Search

We address the problems of constructing the Voronoi diagram (VD) and Delaunay triangulation (DT) of points in the plane with mutually dependent location uncertainties, testing their stability, and computing their components. Point coordinate uncertainties are modeled with the Linear Parametric Geometric Uncertainty Model (LPGUM), a deterministic, expressive and computationally efficient first order linear approximation of geometric uncertainty that supports parametric dependencies between point locations. We define an uncertain three-point circle and its properties and present in-circle-test algorithms for the dependent and the independent cases whose respective time complexity is O (P 4 (k)) and O (k log k) , where k is the number of parameters that describe the points location uncertainty and P 4 (k) is the complexity of quartic k -variable optimization. We define the uncertain VD and DT of n LPGUM points and show that an unstable VD may have an exponential number of topologically different instances. We describe algorithms for testing VD and DT stability whose time complexity is O (n P 4 (k)) and O (n k log k) for the dependent and independent cases when the nominal (exact) VD is given. We present algorithms to compute the vertices, edges, and faces of uncertain VD and DT for the independent case whose complexity is O (n k 2 log k + n log n) time and O (n k) space. Finally, we describe algorithms for answering exact and uncertain point location queries in a stable uncertain VD and for dynamically updating it in O (k 2 log k + log n) and O (k 2 log k + log n + P 4 (k)) average case time complexity for the independent and dependent cases. [ABSTRACT FROM AUTHOR]

We study the shortest k -violation path problem in a simple polygon. Let P be a simple polygon in ℝ 2 with n vertices and let s , t be a pair of points in P. Let i n t (P) represent the interior of P. Let P ̃ = ℝ 2 \ i n t (P) represent the exterior of P. For an integer k ≥ 0 , the shortest k -violation path problem in P is the problem of computing the shortest path from s to t in P , such that at most k path segments are allowed to be in P ̃. The subpaths of a k -violation path are not allowed to bend in P ̃. For any k , we present a (1 + 2 𝜖) factor approximation algorithm for the problem that runs in O (n 2 σ 2 k log n 2 σ 2 + n 2 σ 2 k) time. Here σ = O (log δ (L r)) and δ , L , r are geometric parameters. [ABSTRACT FROM AUTHOR]

Let X n be a planar Poisson point process of intensity n. We give a new proof that the expected length of the Voronoi path between (0 , 0) and (1 , 0) in the Delaunay triangulation associated with X n is 4 π ≃ 1. 2 7 when n goes to infinity; and we also prove that the variance of this length is Θ (1 / n). We investigate the length of possible shortcuts in this path, and define a shortened Voronoi path whose expected length can be expressed as an integral that is numerically evaluated to ≃ 1. 1 6. The shortened Voronoi path has the property to be locally defined; and is shorter than the previously known locally defined paths in Delaunay triangulation such as the upper path whose expected length is 3 5 / 3 π 2 ≃ 1. 1 8. [ABSTRACT FROM AUTHOR]

We describe an algorithm to triangulate a general 3-dimensional-map on an arbitrary space in such way that the resulting 3-dimensional triangulation is vertex-colorable with four colors. (Four-colorable triangulations can be efficiently represented and manipulated by the GEM data structure of Montagner and Stolfi.) The standard solution to this problem is the barycentric subdivision (BCS) of the map. Our algorithm yields a 4-colored triangulation that is provably smaller than the BCS, and in practice is often a small fraction of its size. When the input map is a shellable triangulation of a 3-ball, in particular, we can prove that the output size is less than times the size of the BCS. [ABSTRACT FROM AUTHOR]

Let be a graph, be a source node and be a target node. The sequence of adjacent nodes (graph walk) visited by a routing algorithm is a -competitive route if its length in is at most times the length of the shortest path from to in . We present a -competitive online routing algorithm on the Delaunay triangulation of an arbitrary given set of points in the plane. This improves the competitive ratio on Delaunay triangulations from the previous best of . We also present a -competitive online routing algorithm for Delaunay triangulations of point sets in convex position. [ABSTRACT FROM AUTHOR]

A greedily routable region (GRR) is a closed subset of , in which any destination point can be reached from any starting point by always moving in the direction with maximum reduction of the distance to the destination in each point of the path. Recently, Tan and Kermarrec proposed a geographic routing protocol for dense wireless sensor networks based on decomposing the network area into a small number of interior-disjoint GRRs. They showed that minimum decomposition is NP-hard for polygonal regions with holes. We consider minimum GRR decomposition for plane straight-line drawings of graphs. Here, GRRs coincide with self-approaching drawings of trees, a drawing style which has become a popular research topic in graph drawing. We show that minimum decomposition is still NP-hard for graphs with cycles and even for trees, but can be solved optimally for trees in polynomial time, if we allow only certain types of GRR contacts. Additionally, we give a 2-approximation for simple polygons, if a given triangulation has to be respected. [ABSTRACT FROM AUTHOR]

Selection lemmas are classical results in discrete geometry that have been well studied and have applications in many geometric problems like weak epsilon nets and slimming Delaunay triangulations. Selection lemma type results typically show that there exists a point that is contained in many objects that are induced (spanned) by an underlying point set. In the first selection lemma, we consider the set of all the objects induced by a point set . This question has been widely explored for simplices in , with tight bounds in . In our paper, we prove first selection lemma for other classes of geometric objects like boxes and balls in . We also consider the strong variant of this problem where we add the constraint that the piercing point comes from . We prove an exact result on the strong and the weak variant of the first selection lemma for axis-parallel rectangles and disks (for centrally symmetric point sets). We also show non-trivial bounds on the first selection lemma for axis-parallel boxes and balls in . In the second selection lemma, we consider an arbitrary sized subset of the set of all objects induced by . We study this problem for axis-parallel rectangles and show that there exists a point in the plane that is contained in rectangles. This is an improvement over the previous bound by Smorodinsky and Sharir22 when is almost quadratic. [ABSTRACT FROM AUTHOR]

(I) We exhibit a set of 23 points in the plane that has dilation at least , improving the previous best lower bound of for the worst-case dilation of plane spanners. (II) For every , there exists an -element point set such that the degree dilation of equals in the domain of plane geometric spanners. In the same domain, we show that for every , there exists a an -element point set such that the degree dilation of equals The previous best lower bound of holds for any degree. (III) For every , there exists an -element point set such that the stretch factor of the greedy triangulation of is at least . [ABSTRACT FROM AUTHOR]

We describe an algorithm to triangulate a general map on an arbitrary surface in such way that the resulting triangulation is vertex-colorable with three colors. (Three-colorable triangulations can be efficiently represented and manipulated by the GEM data structure of Montagner and Stolfi.) The standard solution to this problem is the barycentric subdivision, which produces triangles when applied to a map with edges, such that of them are border edges (adjacent to only one face). Our algorithm yields a subdivision with at most triangles, where is the Euler Characteristic of the surface; or at most triangles if all faces of the map have the same degree . Experimental results show that the resulting triangulations have, on the average, significantly fewer triangles than these upper bounds. [ABSTRACT FROM AUTHOR]

Deciding 3-colorability for general plane graphs is known to be an NP-complete problem. However, for certain families of graphs, like triangulations, polynomial time algorithms exist. We consider the family of pseudo-triangulations, which are a generalization of triangulations, and prove NP-completeness for this class. This result also holds if we bound their face degree to four, or exclusively consider pointed pseudo-triangulations with maximum face degree five. In contrast to these completeness results, we show that pointed pseudo-triangulations with maximum face degree four are always 3-colorable. An according 3-coloring can be found in linear time. Some complexity results relating to the rank of pseudo-triangulations are also given. [ABSTRACT FROM AUTHOR]

We study the problem of visibility in polyhedral terrains in the presence of multiple viewpoints. We consider a triangulated terrain with m > 1 viewpoints (or guards) located on the terrain surface. A point on the terrain is considered visible if it has an unobstructed line of sight to at least one viewpoint. We study several natural and fundamental visibility structures: (1) the visibility map, which is a partition of the terrain into visible and invisible regions; (2) the colored visibility map, which is a partition of the terrain into regions whose points have exactly the same visible viewpoints; and (3) the Voronoi visibility map, which is a partition of the terrain into regions whose points have the same closest visible viewpoint. We study the complexity of each structure for both 1.5D and 2.5D terrains, and provide efficient algorithms to construct them. Our algorithm for the visibility map in 2.5D terrains improves on the only existing algorithm in this setting. To the best of our knowledge, the other structures have not been studied before. [ABSTRACT FROM AUTHOR]

In this paper we consider the ip operation for combinatorial pointed pseudotriangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs.We show that every combinatorial 4-PPT is stretchable to a geometric pseudo-triangulation, which in general is not the case if faces may have size larger than 4. Moreover, we prove that the ip graph of combinatorial 4-PPTs is connected and has diameter O( n2), even in the case of labeled vertices with fixed outer face. For this case we provide an Ω(n log n) lower bound. [ABSTRACT FROM AUTHOR]