Dynamic Point Location in General Subdivisions

The dynamic planar point location problem is the task of maintaining a dynamic set S of n nonintersecting (except possibly at endpoints) line segments in the plane under the following operations:

• Locate (: point): Report the segment immediately above , i.e., the first segment intersected by an upward vertical ray starting at ;

• Insert (: segment): Add segment to the collection of segments;

• Delete (: segment): Remove segment from the collection of segments.

We present a solution which requires space O(n) and has query and insertion time O(log n log log n) and deletion time O(log²n). The bounds for insertions and deletions are amortized. A query time below O(log²n) was previously only known for monotone subdivisions and subdivisions consisting of horizontal segments and required nonlinear space.     

Improved heuristics for the minimum weight triangulation problem

Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n ³) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases.     

A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation

We present a simple new algorithm for triangulating polygons and planar straightline graphs, It provides "shape" and "size" guarantees:

• All triangles have a bounded aspect ratio.

• The number of triangles is within a constant factor of optimal.

Such "quality" triangulations are desirable as meshes for the finite element method, in which the running time generally increases with the number of triangles, and where the convergence and stability may be hurt by very skinny triangles. The technique we use-successive refinement of a Delaunay triangulation-extends a mesh generation technique of Chew by allowing triangles of varying sizes. Compared with previous quadtree-based algorithms for quality mesh generation, the Delaunay refinement approach is much simpler and generally produces meshes with fewer triangles. We also discuss an implementation of the algorithm and evaluate its performance on a variety of inputs.     

A new asymmetric inclusion region for minimum weight triangulation

As a global optimization problem, planar minimum weight triangulation problem has attracted extensive research attention. In this paper, a new asymmetric graph called one-sided β-skeleton is introduced. We show that the one-sided circle-disconnected (?2b){(\sqrt{2}\beta)} -skeleton is a subgraph of a minimum weight triangulation. An algorithm for identifying subgraph of minimum weight triangulation using the one-sided (?2b){(\sqrt{2}\beta)} -skeleton is proposed and it runs in O(n^4/3+e+min{klogn, n²logn}){O(n^{4/3+\epsilon}+\min\{\kappa \log n, n^2\log n\})} time, where κ is the number of intersected segmented between the complete graph and the greedy triangulation of the point set.     

Trade-off between sample size and accuracy: Case of measurements under interval uncertainty

In many practical situations, we are not satisfied with the accuracy of the existing measurements. There are two possible ways to improve the measurement accuracy:

• First, instead of a single measurement, we can make repeated measurements; the additional information coming from these additional measurements can improve the accuracy of the result of this series of measurements.

• Second, we can replace the current measuring instrument with a more accurate one; correspondingly, we can use a more accurate (and more expensive) measurement procedure provided by a measuring lab – e.g., a procedure that includes the use of a higher quality reagent.

In general, we can combine these two ways, and make repeated measurements with a more accurate measuring instrument. What is the appropriate trade-off between sample size and accuracy? This is the general problem that we address in this paper.     

Orthogonal polynomials and Gaussian quadrature for refinable weight functions

We show how to compute the modified moments of a refinable weight function directly from its mask in O(N²n) rational operations, where N is the desired number of moments and n the length of the mask. Three immediate applications of such moments are:

• the expansion of a refinable weight function as a Legendre series;

• the generation of the polynomials orthogonal with respect to a refinable weight function;

• the calculation of Gaussian quadrature formulas for refinable weight functions.

In the first two cases, all operations are rational and can in principle be performed exactly.

Space Efficient Suffix Trees

We give first the representation of a suffix tree that uses n lg n + O(n) bits of space and supports searching for a pattern string in the given text (from a fixed size alphabet) in O(m) time, where n is the size of the text and m is the length of the pattern. The structure is quite simple and answers a question raised by Muthukrishnan (in Proceedings of the FST and TCS Preconference Workshop on Randomization, 1997, pp. 23–27). Previous compact representations of suffix trees had either a higher lower order term in space and had some expectation assumption or required more time for searching. When the size of the alphabet k is not viewed as a constant, this structure can be modified to use the same space but take O(m lg k) time for string searching or to use an additional O(n lg k) bits but take the same O(m) time for searching. We then give several index structures for binary texts, with less space including

• a structure that uses a suffix array (lg  bits) and an additional () bits,

• an indexing structure that takes bits of space, and

• an ( lg ) bit structure which answers in () time, the decision question of whether a given pattern of length occurs in the text.

Each of these structures uses a different technique, either in the storage scheme or in the search algorithm, in reducing the space requirement. The first one uses a suffix array, a sparse suffix tree, and a table structure. Finding all the occurrences of a pattern using this structure takes O(m + s) time, where s is the number of occurrences of the pattern in the text. The second structure constructs a sparse suffix tree for all the suffixes that start with the bit that occurs more times in the given binary text. The last structure uses an iterative algorithm to search for the pattern. This structure is the first o(n lg n) bit index to support the decision version of indexing queries in time linear in the length of the pattern. But this does not support the general indexing queries where we want to find the position of the occurrence of the pattern.Our main contribution is the development of techniques to use the succinct tree representation through balanced parentheses for suffix trees.     

Application of semi-definite programming to robust stability of delay systems

We study here robust stability of linear systems with several uncertain incommensurate delays, more precisely the property usually called delay-dependent stability. The main result of this paper consists in establishing that the latter is equivalent to the feasibility of some Linear Matrix Inequality (LMI), a convex optimization problem whose numerical solution is well documented.The method is based on two main techniques:

• use of Padé approximation to transform the system into some singularly perturbed finite-dimensional system, for which robust dichotomy has to be checked;

• recursive applications of Generalized Kalman–Yakubovich–Popov (KYP) lemma to characterise by an LMI the previous property.

Approximating the minimum weight steiner triangulation

We show that the length of the minimum weight Steiner triangulation (MWST) of a point set can be approximated within a constant factor by a triangulation algorithm based on quadtrees. InO(n logn) time we can compute a triangulation withO(n) new points, and no obtuse triangles, that approximates the MWST. We can also approximate the MWST with triangulations having no sharp angles. We generalize some of our results to higher-dimensional triangulation problems. No previous polynomial-time triangulation algorithm was known to approximate the MWST within a factor better thanO(logn).     

Character sets of strings

Given a string S over a finite alphabet Σ, the character set (also called the fingerprint) of a substring S^′ of S is the subset CΣ of the symbols occurring in S^′. The study of the character sets of all the substrings of a given string (or a given collection of strings) appears in several domains such as rule induction for natural language processing or comparative genomics. Several computational problems concerning the character sets of a string arise from these applications, especially:

(1) Output all the maximal locations of substrings having a given character set.

(2) Output for each character set C occurring in a given string (or a given collection of strings) all the maximal locations of C.

Denoting by n the total length of the considered string or collection of strings, we solve the first problem in Θ(n) time using Θ(n) space. We present two algorithms solving the second problem. The first one runs in Θ(n²) time using Θ(n) space. The second algorithm has Θ(n|Σ|log|Σ|) time and Θ(n) space complexity and is an adaptation of an algorithm by Amir et al. [A. Amir, A. Apostolico, G.M. Landau, G. Satta, Efficient text fingerprinting via Parikh mapping, J. Discrete Algorithms 26 (2003) 1–13].     

Symplectically hyperbolic manifolds

A symplectic form is called hyperbolic if its pull-back to the universal cover is a differential of a bounded one-form. The present paper is concerned with the properties and constructions of manifolds admitting hyperbolic symplectic forms. The main results are:

• If a symplectic form represents a bounded cohomology class then it is hyperbolic.

• The symplectic hyperbolicity is equivalent to a certain isoperimetric inequality.

• The fundamental group of symplectically hyperbolic manifold is non-amenable.

We also construct hyperbolic symplectic forms on certain bundles and Lefschetz fibrations, discuss the dependence of the symplectic hyperbolicity on the fundamental group and discuss some properties of the group of symplectic diffeomorphisms of a symplectically hyperbolic manifold.

Stochastic control of funding systems

This paper is concerned with funding systems, i.e. systems which accumulate funds for the future payment of financial obligations. Commonly, such funding requires a balance between (1) the desire to minimise the contributions that need to be diverted from other use to the support of the Fund, and (2) the need to maintain reasonable solvency in the Fund.Such funding is discussed here in a general framework. Applications are numerous. The specific applications mentioned in the paper are:

• Defined benefit retirement funding,

• Maintenance of a prudential margin by a non-life insurer,

• Dividend payment strategy.

The paper applies stochastic optimal control theory to determine how rates of contribution to the Fund and allocation of its assets by asset sector should respond to changing solvency. These results are obtainable from a particular differential equation, which may be solved numerically. Detailed numerical examples are provided.     

Computing a Minimum Weight Triangulation of a Sparse Point Set*

Investigating the minimum weight triangulation of a point set with constraint is an important approach for seeking the ultimate solution of the minimum weight triangulation problem. In this paper, we consider the minimum weight triangulation of a sparse point set, and present an O(n ⁴) algorithm to compute a triangulation of such a set. The property of sparse point set can be converted into a new sufficient condition for finding subgraphs of the minimum weight triangulation. A special point set is exhibited to show that our new subgraph of minimum weight triangulation cannot be found by any currently known methods.     

Approximation for Minimum Triangulations of Simplicial Convex 3-Polytopes

A minimum triangulation of a convex 3-polytope is a triangulation that contains the minimum number of tetrahedra over all its possible triangulations. Since finding minimum triangulations of convex 3-polytopes was recently shown to be NP-hard, it becomes significant to find algorithms that give good approximation. In this paper we give a new triangulation algorithm with an improved approximation ratio 2 - Ω(1/\sqrt n ) , where n is the number of vertices of the polytope. We further show that this is the best possible for algorithms that only consider the combinatorial structure of the polytopes. Received August 5, 2000, and in revised form March 29, 2001, and May 3, 2001. Online publication October 12, 2001.     

On the minimality of polygon triangulation

The problem of triangulating a polygon using the minimum number of triangles is treated. We show that the minimum number of triangles required to partition a simplen-gon is equal ton+2w –d – 2, wherew is the number of holes andd is the maximum number of independent degenerate triangles of then-gon. We also propose an algorithm for constructing the minimum triangulation of a simple hole-freen-gon. The algorithm takesO(nlog² n+DK ²) time, whereD is the maximum number of vertices lying on the same line in then-gon andK is the number of minimally degenerate triangles of then-gon.     

Greedily Finding a Dense Subgraph

Given an n-vertex graph with nonnegative edge weights and a positive integer k ≤ n, our goal is to find a k-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly k vertices are left. We derive tight bounds on the worst case approximation ratio R of this greedy algorithm: (1/2 + n/2k)² − O(n ^− 1/3) ≤ R ≤ (1/2 + n/2k)² + O(1/n) for k in the range n/3 ≤ k ≤ n and 2(n/k − 1) − O(1/k) ≤ R ≤ 2(n/k − 1) + O(n/k²) for k < n/3. For k = n/2, for example, these bounds are 9/4 ± O(1/n), improving on naive lower and upper bounds of 2 and 4, respectively. The upper bound for general k compares well with currently the best (and much more complicated) approximation algorithm based on semidefinite programming.     

Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies

The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. A Radiocoloring (RC) of a graph G(V,E) is an assignment function such that |Λ(u)−Λ(v)|2, when u,v are neighbors in G, and |Λ(u)−Λ(v)|1 when the distance of u,v in G is two. The discrete number of frequencies used is called order and the range of frequencies used, span. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span (min span RCP) or the order (min order RCP).In this paper, we deal with an interesting, yet not examined until now, variation of the radiocoloring problem: that of satisfying frequency assignment requests which exhibit some periodic behavior. In this case, the interference graph (modelling interference between transmitters) is some (infinite) periodic graph. Infinite periodic graphs usually model finite networks that accept periodic (in time, e.g. daily) requests for frequency assignment. Alternatively, they can model very large networks produced by the repetition of a small graph.A periodic graph G is defined by an infinite two-way sequence of repetitions of the same finite graph G_i(V_i,E_i). The edge set of G is derived by connecting the vertices of each iteration G_i to some of the vertices of the next iteration G_i+1, the same for all G_i. We focus on planar periodic graphs, because in many cases real networks are planar and also because of their independent mathematical interest.We give two basic results:

• We prove that the min span RCP is PSPACE-complete for periodic planar graphs.

• We provide an O(n(Δ(G_i)+σ)) time algorithm (where|V_i|=n, Δ(G_i) is the maximum degree of the graph G_i and σ is the number of edges connecting each G_i to G_i+1), which obtains a radiocoloring of a periodic planar graph G that approximates the minimum span within a ratio which tends to as Δ(G_i)+σ tends to infinity.

We remark that, any approximation algorithm for the min span RCP of a finite planar graph G, that achieves a span of at most αΔ(G)+constant, for any α and where Δ(G) is the maximum degree of G, can be used as a subroutine in our algorithm to produce an approximation for min span RCP of asymptotic ratio α for periodic planar graphs.

Edit distance with move operations

The traditional edit-distance problem is to find the minimum number of insert-character and delete-character (and sometimes change character) operations required to transform one string into another. Here we consider the more general problem of a string represented by a singly linked list (one character per node) and being able to apply these operations to the pointer associated with a vertex as well as the character associated with the vertex. That is, in O(1) time, not only can characters be inserted or deleted, but substrings can be moved or deleted. We limit our attention to the ability to move substrings and leave substring deletions for future research. Note that O(1) time substring move operation implies O(1) substring exchange operation as well, a form of transformation that has been of interest in molecular biology. We show that this problem is NP-complete, and that a “recursive” sequence of moves can be simulated with at most a constant factor increase by a non-recursive sequence. Although a greedy algorithm is known to have poor (a polynomial factor) worst case performance, we present a polynomial time greedy algorithm for non-recursive moves which on a subclass of instances of a problem of size n achieves an approximation factor to optimal of at most O(logn). The development of this greedy algorithm shows how to reduce moves of substrings to moves of characters, and how to convert moves of characters to only inserts and deletes of characters.     

Enumeration of Planar Constellations

The enumeration of transitive ordered factorizations of a given permutation is a combinatorial problem related to singularity theory. Let n ≥ 1, and let σ₀ be a permutation of _n having d_i cycles of length i, for i ≥ 1. Let m ≥ 2. We prove that the number of m-tuples (σ₁,…,σ_m) of permutation of _n such that

• σσ···σ = σ,

• the group generated by σ,…,σ acts transitively on {1, 2,…,},

• ∑ (σ) = ( − 1) + 2, where (σ) denotes the number of cycles of σ

A one-to-one correspondence relates these m-tuples to some rooted planar maps, which we call constellations and enumerate via a bijection with some bicolored trees. For m = 2, we recover a formula of Tutte for the number of Eulerian maps. The proof relies on the idea that maps are conjugacy classes of trees and extends the method previously applied to Eulerian maps by the second author. Our result might remind the reader of an old theorem of Hurwitz, giving the number of m-tuples of transpositions satisfying the above conditions. Indeed, we show that our result implies Hurwitz' theorem. We also briefly discuss its implications for the enumeration of nonequivalent coverings of the sphere.     

Approximation Algorithms for Dispersion Problems

Given a collection of weighted sets, each containing at most k elements drawn from a finite base set, the k-set packing problem is to find a maximum weight sub-collection of disjoint sets. A greedy algorithm for this problem approximates it to within a factor of k, and a natural local search has been shown to approximate it to within a factor of roughly k − 1. However, neither paradigm can yield approximations that improve on this.We present an approximation algorithm for the weighted k-set packing problem that combines the two paradigms by starting with an initial greedy solution and then repeatedly choosing the best possible local improvement. The algorithm has a performance ratio of 2(k + 1)/3, which we show is asymptotically tight. This is the first asymptotic improvement over the straightforward ratio of k.