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]

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]

In this paper we study proximity graph structures like Delaunay triangulations based on geometric graphs, i.e. graphs which are subgraphs of the complete geometric graph. Given an arbitrary geometric graph G, we define Voronoi diagrams, Delaunay triangulations, relative neighborhood graphs, Gabriel graphs which are related to the graph structure and then study their complexities when G is a general geometric graph or G is some special graph derived from the application area of wireless networks. Besides being of fundamental interest these structures have applications in topology control for wireless networks. [ABSTRACT FROM AUTHOR]

Given an unknown target planar map, we present an algorithm for constructing an approximation of the unknown target based on information gathered from linear probes of the target. Our algorithm is a general purpose reconstruction algorithm that can be applied in many settings. Our algorithm is particularly suited for the setting where computing the intersection of a line with an unknown target is much simpler than computing the unknown target itself. The algorithm maintains a triangulation from which the approximation of the unknown target can be extracted. We evaluate the quality of the approximation with respect to the target both in the topological sense and the metric sense. The correctness of the algorithm and the evaluation of its time complexity are also presented. Finally, we present some experimental results. For example, since generalized Voronoi diagrams are planar maps, our algorithm presents a simpler alternative method for constructing approximations of generalized Voronoi diagrams, which are notoriously difficult to compute. [ABSTRACT FROM AUTHOR]

We use circle-packing methods to generate quadrilateral meshes for polygonal domains, with guaranteed bounds both on the quality and the number of elements. We show that these methods can generate meshes of several types: (1) the elements form the cells of a Voronoï diagram, (2) all elements have two opposite 90° angles, (3) all elements are kites, or (4) all angles are at most 120°. In each case the total number of elements is O(n), where n is the number of input vertices. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]