AnO(n logn) algorithm for the voronoi diagram of a set of simple curve segments

LetX be a given set ofn circular and straight line segments in the plane where two segments may interest only at their endpoints. We introduce a new technique that computes the Voronoi diagram ofX inO(n logn) time. This result improves on several previous algorithms for special cases of the problem. The new algorithm is relatively simple, an important factor for the numerous practical applications of the Voronoi diagram.This work was supported by NSF Grants No. DCR-84-01898 and No. DCR-84-01633.     

Computing the dimension of a semi-algebraic set

In this paper, we consider the problem of computing the real dimension of a given semi-algebraic subset of R ^k, where R is a real closed field. We prove that the dimension k′ of a semi-algebraic set described by s polynomials of degree d in k variables can be computed in time

Digitalizing line segments

We introduce a novel and general approach for digitalization of line segments in the plane that satisfies a set of axioms naturally arising from Euclidean axioms. In particular, we show how to derive such a system of digital segments from any total order on the integers. As a consequence, using a well-chosen total order, we manage to define a system of digital segments such that all digital segments are, in Hausdorff metric, optimally close to their corresponding Euclidean segments, thus giving an explicit construction that resolves the main question of [J. Chun, M. Korman, M. Nöllenburg, and T. Tokuyama. Consistent digital rays. Discrete Comput. Geom., 42(3):359–378, 2009].     

Computing a longest common subsequence for a set of strings

The known 2-string LCS problem is generalized to finding a Longest Common Subsequence (LCS) for a set of strings. A new, general approach that systematically enumerates common subsequences is proposed for the solution. Assuming a finite symbol set, it is shown that the presented scheme requires a preprocessing time that grows linearly with the total length of the input strings and a processing time that grows linearly with (K), the number of strings, and () the number of matches among them. The only previous algorithm for the generalized LCS problem takesO(K·|S ₁|·|S ₂|·...|S _k |) execution time, where |S _i | denotes the length of the stringS _i . Since typically is a very small percentage of |S ₁|·|S ₂|·...·|S _k |, the proposed method may be considered to be much more efficient than the straightforward dynamic programming approach.     

Computing a maxian point of a simple rectilinear polygon

Let P be a simple rectilinear polygon with n vertices. There are k points in P. The maxian problem is to locate a single facility in P so as to maximize the sum of its distance from it to the k points. We present an O((n×k)logn) time algorithm for this problem.     

Computing the link center of a simple polygon

The link center of a simple polygonP is the set of pointsx insideP at which the maximal link-distance fromx to any other point inP is minimized. Here the link distance between two pointsx, y insideP is defined to be the smallest number of straight edges in a polygonal path insideP connectingx toy. We prove several geometric properties of the link center and present an algorithm that calculates this set in timeO(n ²), wheren is the number of sides ofP. We also give anO(n logn) algorithm for finding an approximate link center, that is, a pointx such that the maximal link distance fromx to any point inP is at most one more than the value attained from the true link center.Work on this paper by the second author has been supported by National Science Foundation Grant DMS-8501947. Work by the third author has been supported by the Canadian National Science and Engineering Research Council, Grant A0332. Work by the fifth author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the seventh author has been supported by a Killam Senior Research Fellowship from the Canada Council, and work by the ninth author has been supported by the National Science Foundation Grants DCR-84-01898 and DCR-84-01633. Part of the work on this paper has been carried out at the Workshop on Movable Separability of Sets at the Bellairs Research Institute of McGill University, Barbados, February 1986. Further acknowledgments can be obtained from the tenth author upon request.     

Computing the geodesic center of a simple polygon

The geodesic center of a simple polygon is a point inside the polygon which minimizes the maximum internal distance to any point in the polygon. We present an algorithm which calculates the geodesic center of a simple polygon withn vertices in timeO(n logn).Work on this paper by the first author has been supported by National Science Foundation Grant No. DMS-8501947. Work on this paper by the second author has been supported by Office of Naval Research Grant No. N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Part of the work on this paper by the first two authors has been carried out at the Workshop on Movable Separability of Sets at the Bellairs Research Institute of McGill University, Barbados, February 1986. Work on this paper by the third author has been supported by the Fonds zur Förderung der wissenschaftlichen Forschung (FWF), Project S32/01.     

Computing the minimal covering set

We present the first polynomial-time algorithm for computing the minimal covering set of a (weak) tournament. The algorithm draws upon a linear programming formulation of a subset of the minimal covering set known as the essential set. On the other hand, we show that no efficient algorithm exists for two variants of the minimal covering set–the minimal upward covering set and the minimal downward covering set–unless P equals NP. Finally, we observe a strong relationship between von Neumann–Morgenstern stable sets and upward covering on the one hand, and the Banks set and downward covering on the other.     

Computing simple paths among obstacles

Given a set X of points in the plane, two distinguished points s,tX, and a set Φ of obstacles represented by line segments, we wish to compute a simple polygonal path from s to t that uses only points in X as vertices and avoids the obstacles in Φ. We present two results: (1) we show that finding such simple paths among arbitrary obstacles is NP-complete, and (2) we give a polynomial-time algorithm that computes simple paths when the obstacles form a simple polygon P and X is inside P. Our algorithm runs in time O(m²n²), where m is the number of vertices of P and n is the number of points in X.     

A dense planar point set from iterated line intersections

Given S₁, a starting set of points in the plane, not all on a line, we define a sequence of planar point sets {S_i}_i=1^∞ as follows. With S_i already determined, let L_i be the set of all the lines determined by pairs of points from S_i, and let S_i+1 be the set of all the intersection points of lines in L_i. We show that with the exception of some very particular starting configurations, the limiting point set _i=1^∞S_i is everywhere dense in the plane.     

Chebyshev approximation of a point set by a straight line

The problem of calculating the best approximating straight line—in the sense of Chebyshev—to a finite set of points inR ⁿ is considered. First-and second-order optimality conditions are derived and analysed. Lipschitz optimization techniques can be used to find a global minimizer.Communicated by Dietrich Braess.     

Computing a centerpoint of a finite planar set of points in linear time

The notion of a centerpoint of a finite set of points in two and higher dimensions is a generalization of the concept of the median of a set of reals. In this paper we present a linear-time algorithm for computing a centerpoint of a set ofn points in the plane, which is optimal compared with theO(n log³ n) complexity of the previously best-known algorithm. We use suitable modifications of the hamsandwich cut algorithm in [Me2] and the prune-and-search technique of Megiddo [Me1] to achieve this improvement.     

Storing line segments in partition trees

We design two variants of partition trees, calledsegment partition trees andinterval partition trees, that can be used for storing arbitrarily oriented line segments in the plane in an efficient way. The raw structures useO(n logn) andO(n) storage, respectively, and their construction time isO(n logn). In our applications we augment these structures by certain (simple) auxiliary structures, which may increase the storage and preprocessing time by a polylogarithmic factor. It is shown how to use these structures for solving line segment intersection queries, triangle stabbing queries and ray shooting queries in reasonably efficient ways. If we use the conjugation tree as the underlying partition tree, the query time for all problems isO(n ), where=log₂(1+5)–10.695. The techniques are fairly simple and easy to understand.Research of the first author was partially supported by the ESPRIT II Basic Research Action of the EC under contract No. 3075 (Project ALCOM).Work by the third author has been supported in part by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484, and by grants from the Digital Equipment Corporation, the IBM Corporation, the U.S.-Israeli Binational Science Foundation, the NCRD — the Israeli National Council for Research and Development, and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences.     

Location game on disjoint line segments

Two players are endowed with resources for setting up N locations on K line segments of identical length, with N > K ≥ 1. The players alternately choose these locations (possibly in batches of more than one in each round) in order to secure the area closer to their locations than that of their rival’s. The player with the highest secured area wins the game and otherwise the game ends in a tie. Earlier research has shown that, if an analogous game is played on disjoint circles, the second mover advantage is in place only if K = 1, while for K > 1 both players have a tying strategy. It was also shown that these results hold for line segments of identical length when rules of the game additionally require players to take exactly one location in the first round. In this paper we show that the second mover advantage is still in place for K ≥ 1 and 2K − 1 ≤ N, even if the additional restriction is dropped, while K ≤ N < 2K − 1 results in the first mover advantage. Our results allow us to draw conclusions about a natural variant of the game, where the resource mobility constraint is more stringent so that in each round each player chooses a single location and we show that the second mover advantage re-appears for K ≤ N < 2K − 1 if K is an even number. In all the cases the losing player has a strategy guaranteeing him arbitrarily small loss.     

On circuits and pancyclic line graphs

Clark proved that L(G) is hamiltonian if G is a connected graph of order n ≥ 6 such that deg u + deg v ≥ n – 1 – p(n) for every edge uv of G, where p(n) = 0 if n is even and p(n) = 1 if n is odd. Here it is shown that the bound n – 1 – p(n) can be decreased to (2n + 1)/3 if every bridge of G is incident with a vertex of degree 1, which is a necessary condition for hamiltonicity of L(G). Moreover, the conclusion that L(G) is hamiltonian can be strengthened to the conclusion that L(G) is pancyclic. Lesniak-Foster and Williamson proved that G contains a spanning closed trail if |V(G)| = n ≥ 6, δ(G) ≥ 2 and deg u + deg v ≥ n – 1 for every pair of nonadjacent vertices u and v. The bound n – 1 can be decreased to (2n + 3)/3 if G is connected and bridgeless, which is necessary for G to have a spanning closed trail.