Noncrossing Hamiltonian paths in geometric graphs

A geometric graph is a graph embedded in the plane in such a way that vertices correspond to points in general position and edges correspond to segments connecting the appropriate points. A noncrossing Hamiltonian path in a geometric graph is a Hamiltonian path which does not contain any intersecting pair of edges. In the paper, we study a problem asked by Micha Perles: determine the largest number h(n) such that when we remove any set of h(n) edges from any complete geometric graph on n vertices, the resulting graph still has a noncrossing Hamiltonian path. We prove that . We also establish several results related to special classes of geometric graphs. Let h₁(n) denote the largest number such that when we remove edges of an arbitrary complete subgraph of size at most h₁(n) from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We prove that . Let h₂(n) denote the largest number such that when we remove an arbitrary star with at most h₂(n) edges from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We show that h₂(n)=⌈n/2⌉-1. Further we prove that when we remove any matching from a complete geometric graph the resulting graph will have a noncrossing Hamiltonian path.     

Ramsey-Type Results for Geometric Graphs, II

We show that for any two-coloring of the segments determined by n points in the plane, one of the color classes contains noncrossing cycles of lengths . This result is tight up to a multiplicative constant. Under the same assumptions, we also prove that there is a noncrossing path of length Ω(n ^2/3 ) , all of whose edges are of the same color. In the special case when the n points are in convex position, we find longer monochromatic noncrossing paths, of length . This bound cannot be improved. We also discuss some related problems and generalizations. In particular, we give sharp estimates for the largest number of disjoint monochromatic triangles that can always be selected from our segments. Received March 25, 1997, and in revised form March 5, 1998.     

On graphs preserving rectilinear shortest paths in the presence of obstacles

In physical VLSI design, network design (wiring) is the most time-consuming phase. For solving global wiring problems, we propose to first compute from the layout geometry a graph that preserves all shortest paths between pairs of relevant points, and then to operate on that graph for computing shortest paths, Steiner minimal tree approximations, or the like. For a set of points and a set of simple orthogonal polygons as obstacles in the plane, withn input points (polygon corner or other) altogether, we show how a shortest paths preserving graph of sizeO(n logn) can be computed in timeO(n logn) in the worst case, with spaceO(n). We illustrate the merits of this approach with a simple example: If the length of a longest edge in the graph is bounded by a polynomial inn, an assumption that is clearly fulfilled for graphs derived from VLSI layout geometries, then a shortest path can be computed in timeO(n logn log logn) in the worst case; this result improves on the known best one ofO(n(logn)^3/2).     

Pointed binary encompassing trees: Simple and optimal

For n disjoint line segments in the plane we construct in optimal O(nlogn) time and linear space an encompassing tree of maximum degree three such that at every vertex v all edges of the tree that are incident to v lie in a halfplane bounded by the line through the input segment which v is an endpoint of. In particular, this tree is pointed since every vertex has an incident angle greater than π. Such a pointed binary tree can be augmented to a minimum pseudo-triangulation. It follows that every set of disjoint line segments in the plane has a constrained minimum pseudo-triangulation whose maximum vertex degree is bounded by a constant.     

Computing the extreme distances between two convex polygons

A polygon in the plane is convex if it contains all line segments connecting any two of its points. Let P and Q denote two convex polygons. The computational complexity of finding the minimum and maximum distance possible between two points p in P and q in Q is studied. An algorithm is described that determines the minimum distance (together with points p and q that realize it) in O(logm + logn) time, where m and n denote the number of vertices of P and Q, respectively. This is optimal in the worst case. For computing the maximum distance, a lower bound $\text{Ω(m + n)}$ is proved. This bound is also shown to be best possible by establishing an upper bound of O(m + n).     

Extremal problems on triangle areas in two and three dimensions

The study of extremal problems on triangle areas was initiated in a series of papers by Erd?s and Purdy in the early 1970s. In this paper we present new results on such problems, concerning the number of triangles of the same area that are spanned by finite point sets in the plane and in 3-space, and the number of distinct areas determined by the triangles.In the plane, our main result is an O(n44/19)=O(n^2.3158) upper bound on the number of unit-area triangles spanned by n points, which is the first breakthrough improving the classical bound of O(n7/3) from 1992. We also make progress in a number of important special cases. We show that: (i) For points in convex position, there exist n-element point sets that span Ω(nlogn) triangles of unit area. (ii) The number of triangles of minimum (nonzero) area determined by n points is at most ; there exist n-element point sets (for arbitrarily large n) that span (6/π²−o(1))n² minimum-area triangles. (iii) The number of acute triangles of minimum area determined by n points is O(n); this is asymptotically tight. (iv) For n points in convex position, the number of triangles of minimum area is O(n); this is asymptotically tight. (v) If no three points are allowed to be collinear, there are n-element point sets that span Ω(nlogn) minimum-area triangles (in contrast to (ii), where collinearities are allowed and a quadratic lower bound holds).In 3-space we prove an O(n17/7β(n))=O(n^2.4286) upper bound on the number of unit-area triangles spanned by n points, where β(n) is an extremely slowly growing function related to the inverse Ackermann function. The best previous bound, O(n8/3), is an old result of Erd?s and Purdy from 1971. We further show, for point sets in 3-space: (i) The number of minimum nonzero area triangles is at most n²+O(n), and this is worst-case optimal, up to a constant factor. (ii) There are n-element point sets that span Ω(n4/3) triangles of maximum area, all incident to a common point. In any n-element point set, the maximum number of maximum-area triangles incident to a common point is O(n4/3+ε), for any ε>0. (iii) Every set of n points, not all on a line, determines at least Ω(n2/3/β(n)) triangles of distinct areas, which share a common side.     

Rectilinear shortest paths in the presence of rectangular barriers

In this paper we address the following shortest-path problem. Given a point in the plane andn disjoint isothetic rectangles (barriers), we want to construct a shortestL ₁ path (not crossing any of the barriers) from the source point to any given query point. A restricted version of this problem (where the source and destination points are knowna priori) had been solved earlier inO(n ²) time. Our approach consists of preprocessing the source point and the barriers to obtain a planar subdivision where a query point can be located and a shortest path connecting it to the source point quickly transvered. By showing that any such path is monotone in at least one ofx ory directions, we are able to apply a plane sweep technique to divide the plane intoO(n) rectangular regions. This leads to an algorithm whose complexity isO(n logn) preprocessing time,O(n) space, andO(logn+k) query time, wherek is the number of turns on the reported path. If only the length of the path is sought,O(logn) query time suffices. Furthermore, we show an (n logn) time lower bound for the case where the source and destination points are known in advance, which implies the optimality of our algorithm in this case.A preliminary version of this paper appeared in theProceedings of the First Symposium on Computational Geometry (1985).Supported in part by CNPq-Conselho Nacional de Desenvolvimento Científico e Tecnológico (Brazil).Supported in part by the National Science Foundation under Grants MCS 8420814 and ECS 8340031.     

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.     

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.     

On rectangular visibility

Given a set of n points in the plane, two points are said to be rectangularly visible if the orthogonal rectangle with the two points as opposite vertices has no other point of the set in its interior. In this paper it is shown that all pairs of rectangularly visible points in a set of size n can be determined in O(n log n + k) time, where k is the number of reported pairs, using O(n) space. Also, we consider the query problem: Given a set V of points and an arbitrary point p, determine those points in V that are rectangularly visible from p. A dynamic data structure is described that uses O(n log n) space, has a query time of O(k + log²n) and an update time of O(log³ n). Additionally, we extend the results to the 3-dimensional case.     

Polyhedral line transversals in space

Algorithms are developed for determining if a set of polyhedral objects inR ³ can be intersected by a common transversal (stabbing) line. It can be determined inO(n logn) time if a set ofn line segments in space has a line transversal, and such a transversal can be found in the same time bound. For a set of polyhedra with a total ofn vertices, we give anO(n ⁴ logn) algorithm for determining the existence of, and computing, a line transversal. Helly-type theorems for lines and segments are also given. In particular, it is shown that if every six of a set of lines in space are intersected by a common transversal, then the entire set has a common transversal.     

Rectilinear line segment intersection,layered segment trees,and dynamization

The aim of the present paper is to provide an efficient solution to the following problem: “Given a family of n rectilinear line segments in two-space report all intersections in the family with a query consisting of an arbitrary rectilinear line segment.” We provide an algorithm which takes O(nlog₂n) preprocessing time, o(nlog₂n) space and O(log₂n + k) query time, where k is the number of reported intersections. This solution serves to introduce a powerful new data structure, the layered segment tree, which is of independent interest. Second it yields, by way of recent dynamization techniques, a solution to the on-line version of the above problem, that is the operations INSERT and DELETE and QUERY with a line segment are allowed. Third it also yields a new nonscanning solution to the batched version of the above problem. Finally we apply these techniques to the problem obtained by replacing “line segment” by “rectangle” in the above problem, giving an efficient solution in this case also.     

Localized and compact data-structure for comparability graphs

We show that every comparability graph of any two-dimensional poset over n elements (a.k.a. permutation graph) can be preprocessed in O(n) time, if two linear extensions of the poset are given, to produce an O(n) space data-structure supporting distance queries in constant time. The data-structure is localized and given as a distance labeling, that is each vertex receives a label of O(logn) bits so that distance queries between any two vertices are answered by inspecting their labels only. This result improves the previous scheme due to Katz, Katz and Peleg [M. Katz, N.A. Katz, D. Peleg, Distance labeling schemes for well-separated graph classes, Discrete Applied Mathematics 145 (2005) 384-402] by a log n factor.As a byproduct, our data-structure supports all-pair shortest-path queries in O(d) time for distance-d pairs, and so identifies in constant time the first edge along a shortest path between any source and destination.More fundamentally, we show that this optimal space and time data-structure cannot be extended for higher dimension posets. More precisely, we prove that for comparability graphs of three-dimensional posets, every distance labeling scheme requires Ω(n^1/3) bit labels.     

Segments,rectangles, contours

Two sets H and V of horizontal and vertical segments, respectively, determine a subdivision M of the plane into regions. A nontrivial region is one whose boundary contains an end-portion of nonzero length of at least one segment, and the nontrivial contour of M is the collection of boundaries of nontrivial regions. In this paper we consider several problems pertaining to H and V, such as the construction of the nontrivial contour of M, of the external contour of M, and of a path between two points in the plane avoiding the segments (route-in-a-maze). We show that, if |H| + |V| = n, all of these problems are solved in time O(n log n), by making use of a static data structure, called the adjacency map, which can be searched in time O(log n) and can be constructed in time O(n log n). The algorithms for the nontrivial and external contour are shown to be optimal.     

Approximation of an open polygonal curve with a minimum number of circular arcs and biarcs

We present an algorithm for approximating a given open polygonal curve with a minimum number of circular arcs. In computer-aided manufacturing environments, the paths of cutting tools are usually described with circular arcs and straight line segments. Greedy algorithms for approximating a polygonal curve with curves of higher order can be found in the literature. Without theoretical bounds it is difficult to say anything about the quality of these algorithms. We present an algorithm which finds a series of circular arcs that approximate the polygonal curve while remaining within a given tolerance region. This series contains the minimum number of arcs of any such series. Our algorithm takes O(n²logn) time for an original polygonal chain with n vertices. Using a similar approach, we design an algorithm with a runtime of O(n²logn), for computing a tangent-continuous approximation with the minimum number of biarcs, for a sequence of points with given tangent directions.     

Partitioning with two lines in the plane

An O(n) algorithm is presented for the problem of partitioning a set of n points in the plane into four equal parts by means of two straight lines.     

The power of geometric duality

This paper uses a new formulation of the notion of duality that allows the unified treatment of a number of geometric problems. In particular, we are able to apply our approach to solve two long-standing problems of computational geometry: one is to obtain a quadratic algorithm for computing the minimum-area triangle with vertices chosen amongn points in the plane; the other is to produce an optimal algorithm for the half-plane range query problem. This problem is to preprocessn points in the plane, so that given a test half-plane, one can efficiently determine all points lying in the half-plane. We describe an optimalO(k + logn) time algorithm for answering such queries, wherek is the number of points to be reported. The algorithm requiresO(n) space andO(n logn) preprocessing time. Both of these results represent significant improvements over the best methods previously known. In addition, we give a number of new combinatorial results related to the computation of line arrangements.