We provide linear-time algorithms for geometric graphs with sublinearly many edge crossings. That is, we provide algorithms running in @math time on connected geometric graphs having @math vertices and @math pairwise crossings, where @math is smaller than @math by an iterated logarithmic factor. Specific problems that we study include Voronoi diagrams and single-source shortest paths. Our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. Instead, our algorithms are based on a planarization method that “zeros in” on edge crossings, together with methods for applying planar separator decompositions to geometric graphs with sublinearly many crossings. Incidentally, our planarization algorithm also solves an open computational geometry problem of Chazelle for triangulating a self-intersecting polygonal chain having @math segments and @math crossings in linear time, for the case when @math is sublinear in @math by an iterated logarithmic factor.
Chazelle @cite_18 shows that any simple polygon can be triangulated in @math time and that this algorithm can be extended to determine in @math time, for any polygonal chain @math , whether or not @math contains a self-intersection. In addition, Chazelle posed as an open problem whether or not one can compute the arrangement of a non-simple polygon in @math time, where @math is the number of pairwise edge crossings. Clarkson, Cole, and Tarjan @cite_7 @cite_31 answer this question in the affirmative for polygons with a super-linear number of crossings, as they give a randomized algorithm that solves this problem in @math expected time. There is, to our knowledge, no previous algorithm that solves Chazelle's open problem, however, for non-simple polygons with a sublinear number of edge crossings.
@cite_18 @cite_31 @cite_7
2113370909 2109556124 2100595965 2171580054
In this paper we study two link distance problems for rectilinear paths inside a simple rectilinear polygon P.First, we present a data structure using O(n log n) storage such that a shortest path between two query points can be computed efficiently. If both query points are vertices of P, the query time is O(1 + l), where l is the number of links. If the query points are arbitrary points inside P, then the query time becomes O(log n + l). The resulting path is not only optimal in the rectilinear link metric, but it is optimal in the L1-metric as well. Secondly, it is shown that the rectilinear link diameter of P can be computed in time O(n log n). We also give an approximation algorithm that runs in linear time. This algorithm produces a solution that differs by at most three links from the exact diameter.The solutions are based on a rectilinear version of Chazelle's polygon cutting theorem. This new theorem states that any simple rectilinear polygon can be cut into two rectilinear subpolygons of size at most 34 times the original size, and that such a cut segment can be found in linear time. This thesis covers work on two topics: unfolding polyhedra into the plane and reconstructing polyhedra from partial information. For each topic, we describe previous work in the area and present an array of new research and results. Our work on unfolding is motivated by the problem of characterizing precisely when overlaps will occur when a polyhedron is cut along edges and unfolded. By contrast to previous work, we begin by classifying overlaps according to a notion of locality. This classification enables us to focus upon particular types of overlaps, and use the results to construct examples of polyhedra with interesting unfolding properties. The research on unfolding is split into convex and non-convex cases. In the non-convex case, we construct a polyhedron for which every edge unfolding has an overlap, with fewer faces than all previously known examples. We also construct a non-convex polyhedron for which every edge unfolding has a particularly trivial type of overlap. In the convex case, we construct a series of example polyhedra for which every unfolding of various types has an overlap. These examples disprove some existing conjectures regarding algorithms to unfold convex polyhedra without overlaps. The work on reconstruction is centered around analyzing the computational complexity of a number of reconstruction questions. We consider two classes of reconstruction problems. The first problem is as follows: given a collection of edges in space, determine whether they can be rearranged by translation only to form a polygon or polyhedron. We consider variants of this problem by introducing restrictions like convexity, orthogonality, and non-degeneracy. All of these problems are NP-complete, though some are proved to be only weakly NP-complete. We then consider a second, more classical problem: given a collection of edges in space, determine whether they can be rearranged by translation and or rotation to form a polygon or polyhedron. This problem is NP-complete for orthogonal polygons, but polynomial algorithms exist for nonorthogonal polygons. For polyhedra, it is shown that if degeneracies are allowed then the problem is NP-hard, but the complexity is still unknown for non-degenerate polyhedra. Assume that an isomorphism between two n-vertex simple polygons, P,Q (with k,l reflex vertices, respectively) is given. We present two algorithms for constructing isomorphic (i.e. adjacency preserving) triangulations of P and Q, respectively. The first algorithm computes isomorphic triangulations of P and Q by introducing at most O((k+l)2) Steiner points and has running time O(n+(k+l)2). The second algorithm computes isomorphic traingulations of P and Q by introducing at most O(kl) Steiner points and has running time O(n+kllog n). The number of Steiner points introduced by the second algorithm is also worst-case optimal. Unlike the O(n2) algorithm of Aronov, Seidel and Souvaine1 our algorithms are sensitive to the number of reflex vertices of the polygons. In particular, our algorithms have linear running time when for the first algorithm, and kl≤n log n for the second algorithm. Recent advances on polygon triangulation have yielded efficient algorithms for a large number of problems dealing with a single simple polygon. If the input consists of several disjoint polygons, however, it is often desirable to merge them in preprocessing so as to produce a single polygon that retains the geometric characteristics of its individual components. We give an efficient method for doing so, which combines a generalized form of Jordan sorting with the efficient use of point location and interval trees. As a corollary, we are able to triangulate a collection of p disjoint Jordan polygonal chains in time O (n + p (log p)1+e), for any fixed e > 0, where n is the total number of vertices. A variant of the algorithm gives a running time of O ((n + p log p) log log p). The performance of these solutions approaches the lower bound of Ω (n + p log p).