A constant-work-space algorithm has read-only access to an input array and may use only O(1) additional words of O(logn) bits, where n is the input size. We show how to triangulate a plane straight-line graph with n vertices in O(n2) time and constant work-space. We also consider the problem of preprocessing a simple polygon P for shortest path queries, where P is given by the ordered sequence of its n vertices. For this, we relax the space constraint to allow s words of work-space. After quadratic preprocessing, the shortest path between any two points inside P can be found in O(n2/s) time.
We devise techniques to manipulate a collection of loosely interpenetrating spheres in three-dimensional space. Our study is motivated by the representation and manipulation of molecular configurations, modeled by a collection of spheres. We analyze the sphere model and point to properties that make it more easy to manipulate than an arbitrary collection of spheres. For this special sphere model we present efficient algorithms for computing its union boundary and for hidden surface removal. The efficiency and practicality of our approach are demonstrated by experiments on actual molecule data.
In the persistent homology of filtrations, the indecomposable decompositions provide the persistence diagrams. However, in almost all cases of multidimensional persistence, the classification of all indecomposable modules is known to be a wild problem. One direction is to consider the subclass of interval-decomposable persistence modules, which are direct sums of interval representations. We introduce the definition of pre-interval representations, a more natural algebraic definition, and study the relationships between pre-interval, interval, and thin indecomposable representations. We show that over the “equioriented” commutative 2D grid, these concepts are equivalent. Moreover, we provide a criterion for determining whether or not an nD persistence module is interval/pre-interval/thin-decomposable without having to explicitly compute decompositions. For 2D persistence modules, we provide an algorithm for determining interval-decomposability, together with a worst-case complexity analysis that uses the total number of intervals in an equioriented commutative 2D grid. We also propose several heuristics to speed up the computation.
DOI : 10.1016/j.comgeo.2022.101879 Anahtar Kelimeler :
Multidimensional persistence, Interval representations, Representation theory
ISSN: 0925-7721 Cilt: 105-106 Sayfa: 101879
Consider k robots initially located at a point inside a region T. Each robot can move anywhere in T independently of the other robots with maximum speed one. The goal of the robots is to evacuate T through an exit at an unknown location on the boundary of T. The objective is to minimize the evacuation time, which is defined as the time the last robot reaches the exit. We consider the face-to-face communication model for the robots: a robot can communicate with another robot only when they meet in T. In this paper, we give upper and lower bounds for the face-to-face evacuation time by k robots that are initially located at the centroid of a unit-sided equilateral triangle or square. For the case of a triangle with k=2 robots, we give a lower bound of 1+2/3≈2.154, and an algorithm with upper bound of 2.3367 on the worst-case evacuation time. We show that for any k, any algorithm for evacuating k≥2 robots requires at least 3 time. This bound is asymptotically optimal, as we show that even a straightforward strategy of evacuation by k robots gives an upper bound of 3+3/k. For k=3 and 4, we give better algorithms with evacuation times of 2.0887 and 1.9816, respectively. For the case of the square and k=2, we give an algorithm with evacuation time of 3.4645 and show that any algorithm requires time at least 3.118 to evacuate in the worst-case. Moreover, for k=3, and 4, we give algorithms with evacuation times 3.1786 and 2.6646, respectively. The algorithms given for k=3 and 4 for evacuation in the triangle or the square can be easily generalized for larger values of k.
In this paper, we propose a new compact and low delay routing labeling scheme for Unit Disk Graphs (UDGs) which often model wireless ad hoc networks. We show that one can assign each vertex of an n-vertex UDG G a compact O(log2n)-bit label such that, given the label of a source vertex and the label of a destination, it is possible to compute efficiently, based solely on these two labels, a neighbor of the source vertex that heads in the direction of the destination. We prove that this routing labeling scheme has a constant hop route-stretch (= hop delay), i.e., for each two vertices x and y of G, it produces a routing path with h(x,y) hops (edges) such that h(x,y)⩽3⋅dG(x,y)+12, where dG(x,y) is the hop distance between x and y in G. To the best of our knowledge, this is the first compact routing scheme for UDGs which not only guaranties delivery but has a low hop delay. Furthermore, our routing labeling scheme has a constant length route-stretch and a constant power route-stretch. To obtain this result, we establish a novel balanced separator theorem for UDGs, which mimics the well-known Lipton and Tarjanʼs planar balanced shortest paths separator theorem. We prove that, in any n-vertex UDG G, one can find two hop-shortest paths P(s,x) and P(s,y) such that the removal of the 3-hop-neighborhood of these paths (i.e., NG3[P(s,x)∪P(s,y)]) from G leaves no connected component with more than 2/3n vertices. This new balanced shortest-paths–3-hop-neighborhood separator theorem allows us to build, for any n-vertex UDG G, a system T(G) of at most 2log32n+2 spanning trees of G such that, for any two vertices x and y of G, there exists a tree T in T(G) with dT(x,y)⩽3⋅dG(x,y)+12. That is, the distances in any UDG can be approximately represented by the distances in at most 2log32n+2 of its spanning trees.
DOI : 10.1016/j.comgeo.2012.01.015 Anahtar Kelimeler :
Unit disk graphs, Collective tree spanners, Routing and distance labeling schemes, Balanced separators, Efficient geometric graph algorithms
ISSN: 0925-7721 Sayı: 7 Cilt: 45 Sayfa: 305-325
There are many representations of planar graphs, but few are as elegant as Turán's (1984): it is simple and practical, uses only 4 bits per edge, can handle self-loops and multi-edges, and can store any specified embedding. Its main disadvantage has been that “it does not allow efficient searching” (Jacobson, 1989). In this paper we show how to add a sublinear number of bits to Turán's representation such that it supports fast navigation while retaining simplicity. As a consequence of the inherited simplicity, we offer the first efficient parallel construction of a compact encoding of a planar graph embedding. Our experimental results show that the resulting representation uses about 6 bits per edge in practice, supports basic navigation operations within a few microseconds, and can be built sequentially at a rate below 1 microsecond per edge, featuring a linear speedup with a parallel efficiency around 50% for large datasets.
DOI : 10.1016/j.comgeo.2020.101630 Anahtar Kelimeler :
Planar embedding, Compact data structures, Parallel construction
ISSN: 0925-7721 Cilt: 89 Sayfa: 101630
How many people can hide in a given terrain, without any two of them seeing each other? We are interested in finding the precise number and an optimal placement of people to be hidden, given a terrain with n vertices. In this paper, we show that this is not at all easy: The problem of placing a maximum number of hiding people is almost as hard to approximate as the Maximum Clique problem, i.e., it cannot be approximated by any polynomial-time algorithm with an approximation ratio of nε for some ε>0, unless P=NP. This is already true for a simple polygon with holes (instead of a terrain). If we do not allow holes in the polygon, we show that there is a constant ε>0 such that the problem cannot be approximated with an approximation ratio of 1+ε.
This paper discusses algorithms for labeling sets of points in the plane, where labels are not restricted to some finite number of positions. We show that continuously sliding labels allow more points to be labeled both in theory and in practice. We define six different models of labeling. We compare models by analyzing how many more points can receive labels under one model than another. We show that maximizing the number of labeled points is NP-hard in the most general of the new models. Nevertheless, we give a polynomial-time approximation scheme and a simple and efficient factor- 12 approximation algorithm for each of the new models. Finally, we give experimental results based on the factor- 12 approximation algorithm to compare the models in practice. We also compare this algorithm experimentally to other algorithms suggested in the literature.
Given two triangulations of a convex polygon, computing the minimum number of flips required to transform one to the other is a long-standing open problem. It is not known whether the problem is in P or NP-complete. We prove that two natural generalizations of the problem are NP-complete, namely computing the minimum number of flips between two triangulations of (1) a polygon with holes; (2) a set of points in the plane.
DOI : 10.1016/j.comgeo.2014.11.001 Anahtar Kelimeler :
Triangulations, Flips, NP-completeness, Rotations, Binary search trees
ISSN: 0925-7721 Cilt: 49 Sayfa: 17-23
This paper studies 3-dimensional visibility representations of graphs in which objects in 3-D correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which classes of simple objects are universal, i.e., powerful enough to represent all graphs. In particular, we show that there is no constant k for which the class of all polygons having k or fewer sides is universal. However, we show by construction that every graph on n vertices can be represented by polygons each having at most 2n sides. The construction can be carried out by an O(n2) algorithm. We also study the universality of classes of simple objects (translates of a single, not necessarily polygonal object) relative to cliques Kn and similarly relative to complete bipartite graphs Kn,m.
This paper presents a novel two-parameter geometric graph, the γ-neighborhood graph. This graph unifies a number of geometric graphs such as the convex hull, the Delaunay triangulation, and in 2D also the Gabriel graph and the circle-based β-skeleton, into a continuous spectrum of geometric graphs that ranges from the void to the complete graph. The two parameters provide for a great flexibility in the analysis of a set of sites. For specific ranges of the parameters, the corresponding graph can be efficiently constructed.
We present geometric conditions that can be used to restrict or eliminate candidate topologies for Euclidean Steiner minimal trees in ℜd, d⩾2. Our emphasis is on conditions that are not restricted to the planar case ( d=2). For trees with a Steiner topology we give restrictions on terminal–Steiner connections that are based on the Voronoi diagram associated with the set of terminal nodes. We then describe more restrictive conditions for trees with a full Steiner topology and show how these conditions can be used to improve implicit enumeration algorithms for finding Euclidean Steiner minimal trees with d>2.
This paper discusses optimization of quality measures over first order Delaunay triangulations. Unlike most previous work, our measures relate to edge-adjacent or vertex-adjacent triangles instead of only to single triangles. We give efficient algorithms to optimize certain measures, including measures related to the area ratio of adjacent triangles, angle between outward normals of adjacent triangles (for polyhedral terrains), and number of convex vertices. Some other measures are shown to be NP-hard. These include maximum vertex degree, number of convex edges, and number of mixed vertices. For the latter two measures we provide, for any constant ε>0, factor (1−ε) approximation algorithms that run in 2O(1/ε)⋅n and 2O(1/ε2)⋅n time (when the Delaunay triangulation is given). For minimizing the maximum vertex degree, the NP-hardness proof provides an inapproximability result. Our results are presented for the class of first order Delaunay triangulations, but also apply to triangulations where for every triangle at least two edges are fixed. The approximation result on maximizing the number of convex edges is also extended to k-th order Delaunay triangulations.
We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes (beyond-planar graphs is a collective term for the primary attempts to generalize the planar graphs) to right-angle crossing (RAC) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every n-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size O(n)×O(n). Then, we show that every n-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size O(n3)×O(n3). Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.
This paper presents an efficient and robust technique for generating global motion paths for a human model in virtual environments. Initially, a scene is discretized using raster hardware to generate an environment map. An obstacle-free cell path sub-optimal according to Manhattan metric is generated between any two cells. Unlike 2D techniques present in literature, the proposed algorithm works for complex 3D environments suitable for video games and architectural walk-throughs. For obstacle avoidance, the algorithm considers both physical dimensions of the human and actions such as jumping, bending, etc. Path smoothening is carried out to keep the cell path as closely as possible to Euclidean straight-line paths.
We show how to utilize the cactus representation of all minimum cuts of a graph to visualize the minimum cuts of a planar graph in a planar drawing. In a first approach the cactus is transformed into a hierarchical clustering of the graph that contains complete information on all the minimum cuts. This approach is then extended to drawings in which the two vertex subsets of every minimum cut are separated by a simple closed curve. While both approaches work with any embedding-preserving drawing algorithm, we specifically discuss bend-minimum orthogonal drawings.
Given a set of n labeled points on Sd, how many combinatorially different geometric triangulations for this point set are there? We show that the logarithm of this number is at most some positive constant times n⌊d/2⌋+1. Evidence is provided that for even dimensions d the bound can be improved to some constant times nd/2.
We show that for m points and n lines in R2, the number of distinct distances between the points and the lines is Ω(m1/5n3/5), as long as m1/2≤n≤m2. We also prove that for any m points in the plane, not all on a line, the number of distances between these points and the lines that they span is Ω(m4/3). The problem of bounding the number of distinct point-line distances can be reduced to the problem of bounding the number of tangent pairs among a finite set of lines and a finite set of circles in the plane, and we believe that this latter question is of independent interest. In the same vein, we show that n circles in the plane determine at most O(n3/2) points where two or more circles are tangent, improving the previously best known bound of O(n3/2logn). Finally, we study three-dimensional versions of the distinct point-line distances problem, namely, distinct point-line distances and distinct point-plane distances. The problems studied in this paper are all new, and the bounds that we derive for them, albeit most likely not tight, are non-trivial to prove. We hope that our work will motivate further studies of these and related problems.
We introduce a generalization of monotonicity. An n-vertex polygon P is rotationally monotone with respect to a point r if there exists a partitioning of the boundary of P into exactly two polygonal chains, such that one chain can be rotated clockwise around r and the other chain can be rotated counterclockwise around r with neither chain intersecting the interior of the polygon. We present the following two results: (1) Given P and a center of rotation r in the plane, we determine in O(n) time whether P is rotationally monotone with respect to r. (2) We can find all the points in the plane from which P is rotationally monotone in O(n) time for convex polygons and in O(n2) time for simple polygons. We show that both algorithms are worst-case optimal by constructing a class of simple polygons with Ω(n2) distinct valid centers of rotation. A direct application of rotational monotonicity is the popular manufacturing technique of clamshell casting, where liquid is poured into a cast and the cast is removed by rotations once the liquid has hardened.
We present a randomized algorithm of expected time complexity O(m23n23log43m + m log2m + n log2n) for computing bi-chromatic farthest neighbors between n red points and m blue points in E3. The algorithm can also be used to compute all farthest neighbors or external farthest neighbors of n points in E3 in O(n43log43n) expected time. Using these procedures as building blocks, we can compute a Euclidean maximum spanning tree or a minimum-diameter two-partition of n points in E3 in O(n43log73n) expected time. The previous best bound for these problems was O(n32log12n). Our algorithms can be extended to higher dimensions. We also propose fast and simple approximation algorithms for these problems. These approximation algorithms produce solutions that approximate the true value with a relative accuracy ε and run in time O(nε(1−k)2log n) or O(nε(1−k)2log2n) in k-dimensional space.
Voronoi diagrams were introduced by R. Klein (1988) as an axiomatic basis of Voronoi diagrams. We show how to construct abstract Voronoi diagrams in time O(n log n) by a randomized algorithm, which is based on Clarkson and Shor's randomized incremental construction technique (1989). The new algorithm has the following advantages over previous algorithms: • •|It can handle a much wider class of abstract Voronoi diagrams than the algorithms presented in by Klein (1989) and, Mehlhorn, Meiser and O'Dúnlaing (1991). • •|It can be adapted to a concrete kind of Voronoi diagram by providing a single basic operation, namely the construction of a Voronoi diagram of five sites. Moreover, all geometric decisions are confined to the basic operation, and using this operation, abstract Voronoi diagrams can be constructed in a purely combinatorial manner.
Guibas conjectured that given a convex polygon P in the xy-plane along with two triangulations of it, T1 and T2 that share no diagonals, it is always possible to assign height values to the vertices of P such that P∪T1∪T2 becomes a convex 3-polytope. Dekster found a counter example but left open the questions of deciding if a given configuration corresponds to a convex 3-polytope, and constructing such realizations when they exist. This paper presents a characterization of realizable configurations for Guibas' conjecture based on work from the area of polytope convexity testing. Our approach to the decision and construction problems is a reduction to a linear-inequality feasibility problem. The approach is also related to methods used for deciding if an arbitrary triangulation of a point set is a regular triangulation. We show two reductions, one based directly on a global convexity condition resulting in number of inequalities that is quadratic in the number of vertices of P, and one based on an equivalent local convexity condition resulting in a linear number of inequalities.
For a set of n points in the plane, this paper presents simple kinetic data structures (KDSs) for solutions to some fundamental proximity problems, namely, the all nearest neighbors problem, the closest pair problem, and the Euclidean minimum spanning tree (EMST) problem. Also, the paper introduces KDSs for maintenance of two well-studied sparse proximity graphs, the Yao graph and the Semi-Yao graph. We use sparse graph representations, the Pie Delaunay graph and the Equilateral Delaunay graph, to provide new solutions for the proximity problems. Then we design KDSs that efficiently maintain these sparse graphs on a set of n moving points, where the trajectory of each point is assumed to be a polynomial function of constant maximum degree s. We use the kinetic Pie Delaunay graph and the kinetic Equilateral Delaunay graph to create KDSs for maintenance of the Yao graph, the Semi-Yao graph, all the nearest neighbors, the closest pair, and the EMST. Our KDSs use O(n) space and O(nlogn) preprocessing time. We provide the first KDSs for maintenance of the Semi-Yao graph and the Yao graph. Our KDS processes O(n2β2s+2(n)) (resp. O(n3β2s+22(n)logn)) events to maintain the Semi-Yao graph (resp. the Yao graph); each event can be processed in amortized time O(logn). Here, βs(n)=λs(n)/n is an extremely slow-growing function and λs(n) is the maximum length of Davenport–Schinzel sequences of order s on n symbols. Our KDS for maintenance of all the nearest neighbors and the closest pair processes O(n2β2s+22(n)logn) events. For maintenance of the EMST, our KDS processes O(n3β2s+22(n)logn) events. For all three of these problems, each event can be handled in amortized time O(logn). Our deterministic kinetic approach for maintenance of all the nearest neighbors improves by an O(log2n) factor the previous randomized kinetic algorithm by Agarwal, Kaplan, and Sharir. Furthermore, our KDS is simpler than their KDS, as we reduce the problem to one-dimensional range searching, as opposed to using two-dimensional range searching as in their KDS. For maintenance of the EMST, our KDS improves the previous KDS by Rahmati and Zarei by a near-linear factor in the number of events.
DOI : 10.1016/j.comgeo.2014.12.002 Anahtar Kelimeler :
Kinetic data structure, All nearest neighbors, Closest pair, Euclidean minimum spanning tree, (Semi-)Yao graph
ISSN: 0925-7721 Sayı: 4 Cilt: 48 Sayfa: 342-359
We define and study the Fréchet distance and the discrete Fréchet distance between two point sets in the plane. One problem based on the well-known Fréchet distance is to find a polygonal curve on a point set with small Fréchet distance or small discrete Fréchet distance to another given polygonal curve. Here, we consider two given point sets and ask if permutations of these point sets exist, such that the Fréchet distance or the discrete Fréchet distance of curves defined by the permutations is small.
DOI : 10.1016/j.comgeo.2021.101842 Anahtar Kelimeler :
Fréchet distance, Similarity between point sets
ISSN: 0925-7721 Cilt: 102 Sayfa: 101842
Controlled Perturbation (CP, for short) is an approach to obtaining efficient and robust implementations of a large class of geometric algorithms using the computational speed of multiple precision floating point arithmetic (compared to exact arithmetic), while bypassing the precision problems by perturbation. It also allows algorithms to be written without consideration of degenerate cases. CP replaces the input objects by a set of randomly perturbed (moved, scaled, stretched, etc.) objects and protects the evaluation of geometric predicates by guards. The execution is aborted if a guard indicates that the evaluation of a predicate with floating point arithmetic may return an incorrect result. If the execution is aborted, the algorithm is rerun on a new perturbation and maybe with a higher precision of the floating point arithmetic. If the algorithm runs to completion, it returns the correct output for the perturbed input. The analysis of CP algorithms relates various parameters: the perturbation amount, the arithmetic precision, the range of input values, and the number of input objects. We present a general methodology for analyzing CP algorithms. It is powerful enough to analyze all geometric predicates that are formulated as signs of polynomials.
The new approach we propose in this paper is a plane partition with similar features to those of the Voronoi Diagram, but the Euclidean minimum distance criterion is replaced for the minimal angle criterion. The result is a new tessellation of the plane in regions called Polar Diagram, in which every site is owner of a polar region as the locus of points with smallest polar angle respect to this site. We prove that polar diagrams, used as preprocessing, can be applied to many problems in Computational Geometry in order to speed up their processing times. Some of these applications are the convex hull, visibility problems, and path planning problems.
The routing number is a graph invariant introduced by Alon, Chung, and Graham in 1994, and it has been studied for trees and other classes of graphs such as hypercubes. It gives the minimum number of routing steps needed to sort a set of distinct tokens, placed one on each vertex, where each routing step swaps a set of disjoint pairs of adjacent tokens. Our main theorem generalizes the known estimate that a rectangular grid graph R with width w(R) and height h(R) satisfies rt(R)∈O(w(R)+h(R)). We show that for the subgraph P of the infinite square lattice enclosed by any convex polygon, we have rt(P)∈O(w(P)+h(P)).
We present the prefix Fréchet similarity as a new measure for similarity of curves which is for instance motivated by evacuation analysis and defined as follows. Given two (polygonal) curves T and T′, we ask for two prefix curves of T and T′ which have a Fréchet distance no larger than a given distance threshold δ≥0 with respect to the L1 metric such that the sum of the lengths of the prefix curves is maximal. As parameterized Fréchet measures as for example the prefix Fréchet similarity are highly unstable regarding the value of the distance threshold δ, we give an algorithm that computes exactly the profile of the prefix Fréchet similarity which means the complete functional relation between δ and the prefix Fréchet similarity of T and T′. This is the first efficient algorithm for computing exactly the whole profile of a parametrized Fréchet distance. While the running time of our algorithm for computing the profile of the prefix Fréchet similarity is O(n3logn), we provide a lower bound of Ω(n2) for the running time of any algorithm computing the profile of the prefix Fréchet similarity, where n denotes the number of segments on T and T′. This implies that our running time is at most a near linear factor away from being optimal.