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]

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]

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]

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]

We present an algorithm that takes as input a finite point set in ℝ m, and performs a perturbation that guarantees that the Delaunay triangulation of the resulting perturbed point set has quantifiable stability with respect to the metric and the point positions. There is also a guarantee on the quality of the simplices: they cannot be too at. The algorithm provides an alternative tool to the weighting or refinement methods to re-move poorly shaped simplices in Delaunay triangulations of arbitrary dimension, but in addition it provides a guarantee of stability for the resulting triangulation. [ABSTRACT FROM AUTHOR]

We introduce a parametrized notion of genericity for Delaunay triangulations which, in particular, implies that the Delaunay simplices of δ-generic point sets are thick. Equipped with this notion, we study the stability of Delaunay triangulations under perturbations of the metric and of the vertex positions. We quantify the magnitude of the perturbations under which the Delaunay triangulation remains unchanged. [ABSTRACT FROM AUTHOR]

This paper deals with the fast computation of straight skeletons of planar straight-line graphs (PSLGs) at an industrial-strength level. We discuss both the theoretical foun-dations of our algorithm and the engineering aspects of our implementation BONE. Our investigation starts with an analysis of the triangulation-based algorithm by Aichholzer and Aurenhammer and we prove the existence of flip-event-free Steiner triangulations. This result motivates a careful generalization of motorcycle graphs such that their inti-mate geometric connection to straight skeletons is maintained. Based on the generalized motorcycle graph, we devise a non-procedural characterization of straight skeletons of PSLGs and we discuss how to obtain a discretized version of a straight skeleton by means of graphics rendering. Most importantly, this generalization allows us to present a fast and easy-to-implement straight-skeleton algorithm. We implemented our algorithm in C++ based on floating-point arithmetic. Extensive benchmarks with our code BONE demonstrate an 0(n log N) time complexity and 0(n) memory footprint on 22 300 datasets of diverse characteristics. This is a linear factor better than the implementation provided by CGAL 4.0, which shows an 0(n² logn) time complexity and an 0(n²) memory footprint; the CGAL code has been the only fully-functional straight-skeleton code so far. In particular, on datasets with ten thousand vertices, BONE requires about 0.2-0.6 seconds instead of 4-7 minutes consumed by the CGAL code, and BONE uses only 20 MB heap memory instead of several gigabytes. We conclude our paper with a discussion of the engineering aspects and principles that make BONE reliable enough to compute the straight skeleton of datasets comprising a few million vertices on a desktop computer. [ABSTRACT FROM AUTHOR]

Over the last decade, there have been several data structures that, given a planar subdi-vision and a probability distribution over the plane, provide a way for answering point location queries that is fine-tuned for the distribution. All these methods suffer from the requirement that the query distribution must be known in advance. We present a new data structure for point location queries in planar triangulations. Our structure is asymptotically as fast as the optimal structures, but it requires no prior information about the queries. This is a 2-D analogue of the jump from Knuth's optimum binary search trees (discovered in 1971) to the splay trees of Sleator and Tarjan in 1985. While the former need to know the query distribution, the latter are statically optimal. This means that we can adapt to the query sequence and achieve the same asymptotic performance as an optimum static structure, without needing any additional information. [ABSTRACT FROM AUTHOR]

We present Delaunay refinement algorithms for estimating local feature size on the input vertices of a 2D piecewise linear complex and on the input vertices and segments of a 3D piecewise linear complex. These algorithms are designed to eliminate the need for a local feature size oracle during quality mesh generation of domains containing acute input angles. In keeping with Ruppert's algorithm, encroachment in these algorithms can be determined through only local information in the current Delaunay triangulation. The algorithms are practical to implement and several examples are given. [ABSTRACT FROM AUTHOR]

Several Representations and Coding schemes have been proposed to represent efficiently 2D triangulations. In this paper, we propose a new practical approach to reduce the main memory space needed to represent an arbitrary triangulation, while maintaining constant time for some basic queries. This work focuses on the connectivity information of the triangulation, rather than the geometric information (vertex coordinates), since the combinatorial data represents the main part of the storage. The main idea is to gather triangles into patches, to reduce the number of pointers by eliminating the internal pointers in the patches and reducing the multiple references to vertices. To accomplish this, we define and use stable catalogs of patches that are closed under basic standard update operations such as insertion and deletion of vertices, and edge flips. We present some bounds and results concerning special catalogs, and some experimental results that exhibit the practical gain of such methods. [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]

We solve several fundamental geometric problems under a new streaming model recently proposed by Ruhl et al.2,15 In this model, in one pass the input stream can be scanned to generate an output stream or be sorted based on a user-defined comparator; all intermediate streams must be of size O(n). We obtain the following geometric results for any fixed constant ϵ > 0: • We can construct 2D convex hulls in O(1) passes with O(nϵ) extra space. • We can construct 3D convex hulls in O(1) expected number of passes with O(nϵ) extra space. • We can construct a triangulation of a simple polygon in O(1) expected number of passes with O(nϵ) extra space, where n is the number of vertices on the polygon. • We can report all k intersections of a set of 2D line segments in O(1) passes with O(nϵ) extra space, if an intermediate stream of size O(n + k) is allowed. We also consider a weaker model, where we do not have the sorting primitive but are allowed to choose a scan direction for every scan pass. Here we can construct a 2D convex hull from an x-ordered point set in O(1) passes with O(nϵ) extra space. [ABSTRACT FROM AUTHOR]

Consider a set X of points in the plane and a set E of non-crossing segments with endpoints in X. One can efficiently compute the triangulation of the convex hull of the points, which uses X as the vertex set, respects E, and maximizes the minimum internal angle of a triangle. In this paper we consider a natural extension of this problem: Given in addition a Steiner pointp, determine the optimal location of p and a triangulation of X ∪ {p} respecting E, which is best among all triangulations and placements of p in terms of maximizing the minimum internal angle of a triangle. We present a polynomial-time algorithm for this problem and then extend our solution to handle any constant number of Steiner points. [ABSTRACT FROM AUTHOR]

Given a set P of n points in the plane, the order-k Delaunay graph is a graph with vertex set P and an edge exists between two points p, q ∈ P when there is a circle through p and q with at most k other points of P in its interior. We provide upper and lower bounds on the number of edges in an order-k Delaunay graph. We study the combinatorial structure of the set of triangulations that can be constructed with edges of this graph. Furthermore, we show that the order-k Delaunay graph is connected under the flip operation when k ≤ 1 but not necessarily connected for other values of k. If P is in convex position then the order-k Delaunay graph is connected for all k ≥ 0. We show that the order-k Gabriel graph, a subgraph of the order-k Delaunay graph, is Hamiltonian for k ≥ 15. Finally, the order-k Delaunay graph can be used to efficiently solve a coloring problem with applications to frequency assignments in cellular networks. [ABSTRACT FROM AUTHOR]

Topology-based methods have been successfully used for the analysis and visualization of piecewise-linear functions defined on triangle meshes. This paper describes a mechanism for extending these methods to piecewise-quadratic functions defined on triangulations of surfaces. Each triangular patch is tessellated into monotone regions, so that existing algorithms for computing topological representations of piecewise-linear functions may be applied directly to the piecewise-quadratic function. In particular, the tessellation is used for computing the Reeb graph, a topological data structure that provides a succinct representation of level sets of the function. [ABSTRACT FROM AUTHOR]

Given a triangulation G, whose vertex set V is a set of n points in the plane, and given a real number γ with 0 < γ < π, we design an O(n)-time algorithm that constructs a connected subgraph G' of G with vertex set V whose maximum degree is at most 14 + ⌈2π/γ⌉. If G is the Delaunay triangulation of V, and γ = 2π/3, we show that G' is a t-spanner of V (for some constant t) with maximum degree at most 17, thereby improving the previously best known degree bound of 23. If G is a triangulation satisfying the diamond property, then for a specific range of values of γ dependent on the angle of the diamonds, we show that G' is a t-spanner of V (for some constant t) whose maximum degree is bounded by a constant dependent on γ. If G is the graph consisting of all Delaunay edges of length at most 1, and γ = π/3, we show that a modified version of the algorithm produces a plane subgraph G' of the unit-disk graph which is a t-spanner (for some constant t) of the unit-disk graph of V, whose maximum degree is at most 20, thereby improving the previously best known degree bound of 25. [ABSTRACT FROM AUTHOR]

We discuss and compare four fixed parameter algorithms for finding the minimum weight triangulation of a simple polygon with (n – k) vertices on the perimeter and k vertices in the interior (hole vertices), that is, for a total of n vertices. All four algorithms rely on the same abstract divide-and-conquer scheme, which is made efficient by a variant of dynamic programming. They are essentially based on two simple observations about triangulations, which give rise to triangle splits and paths splits. While each of the first two algorithms uses only one of these split types, the last two algorithms combine them in order to achieve certain improvements and thus to reduce the time complexity. By discussing this sequence of four algorithms we try to bring out the core ideas as clearly as possible and thus strive to achieve a deeper understanding as well as a simpler specification of these approaches. In addition, we implemented all four algorithms in Java and report results of experiments we carried out with this implementation. [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]

A polyhedral terrain is the graph of a continuous piecewise linear function defined over the triangles of a triangulation in the xy-plane. Two points on or above a terrain are visible to each other if the line-of-sight does not intersect the space below the terrain. In this paper, we look at three related visibility problems in terrains. Suppose we are given a terrain T with n triangles and two regions R1 and R2 on T, i.e., two simply connected subsets of at most m triangles. First, we present an algorithm that determines, for any constant ∊ > 0, within O(n1+∊m) time and storage whether or not R1 and R2 are completely intervisible. We also give an O(m3n4) time algorithm to determine whether every point in R1 sees at least one point in R2. Finally, we present an O(m2n2log n) time algorithm to determine whether there exists a pair of points p ∈ R1 and q ∈ R2, such that p and q see each other. [ABSTRACT FROM AUTHOR]

Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question seems hard to answer; it is not even clear if there exists a lower bound > 1. In this paper we provide the first upper and lower bounds for the embedding problem. 1. Each finite point set can be embedded into the vertex set of a finite triangulation of dilation ≤ 1.1247. 2. Each embedding of a closed convex curve has dilation ≥ 1.00157. 3. Let P be the plane graph that results from intersecting n infinite families of equidistant, parallel lines in general position. Then the vertex set of P has dilation $\geq 2/ \sqrt{3} \approx 1.1547$. [ABSTRACT FROM AUTHOR]

We present a parallel Delaunay refinement algorithm for generating well-shaped meshes in both two and three dimensions. Like its sequential counterparts, the parallel algorithm iteratively improves the quality of a mesh by inserting new points, the Steiner points, into the input domain while maintaining the Delaunay triangulation. The Steiner points are carefully chosen from a set of candidates that includes the circumcenters of poorly-shaped triangular elements. We introduce a notion of independence among possible Steiner points that can be inserted simultaneously during Delaunay refinements and show that such a set of independent points can be constructed efficiently and that the number of parallel iterations is O(log2Δ), where Δ is the spread of the input — the ratio of the longest to the shortest pairwise distances among input features. In addition, we show that the parallel insertion of these set of points can be realized by sequential Delaunay refinement algorithms such as by Ruppert's algorithm in two dimensions and Shewchuk's algorithm in three dimensions. Therefore, our parallel Delaunay refinement algorithm provides the same shape quality and mesh-size guarantees as these sequential algorithms. For generating quasi-uniform meshes, such as those produced by Chew's algorithms, the number of parallel iterations is in fact O(logΔ). To the best of our knowledge, our algorithm is the first provably polylog(Δ) time parallel Delaunay-refinement algorithm that generates well-shaped meshes of size within a constant factor of the best possible. [ABSTRACT FROM AUTHOR]

Given a planar triangulation all of whose faces are initially white, we study the problem of colouring the faces black one by one so that the boundary between black and white faces as well as the number of connected black and white regions are small at all times. We call such a colouring sequence of the triangles a flooding. We prove that a flooding with boundary size ${\mathcal O}({\sqrt n})$ and ${\mathcal O}({\rm log}\,n)$ regions can be computed in ${\mathcal O}(n\,{\rm log}\,n)$ time. We also prove that it is in general impossible to guarantee boundary size ${\mathcal O} (n^{1-\epsilon})$, for any ∊ > 0, and a number of regions that is o(log n), where n is the number of faces of the triangulation. [ABSTRACT FROM AUTHOR]

In this paper we first modify a widely used discrete Laplace-Beltrami operator proposed by Meyer et al over triangular surfaces, and then we show that the modified discrete operator has some convergence properties over the triangulated spheres. A sequence of spherical triangulations which is optimal in certain sense and leads to smaller truncation error of the discrete Laplace-Beltrami operator is constructed. Optimal hierarchical spherical triangulations are also given. Truncation error bounds of the discrete Laplace-Beltrami operator over the constructed triangulations are provided. [ABSTRACT FROM AUTHOR]

We introduce a new algorithm to convert triangular meshes of polygonal regions, with or without holes, into strictly convex quadrilateral meshes of small bounded size. Our algorithm includes all vertices of the triangular mesh in the quadrilateral mesh, but may add extra vertices (called Steiner points). We show that if the input triangular mesh has t triangles, our algorithm produces a mesh with at most $\lfloor\frac{3t}{2}\rfloor+2$ quadrilaterals by adding at most t+2 Steiner points, one of which may be placed outside the triangular mesh domain. We also describe an extension of our algorithm to convert constrained triangular meshes into constrained quadrilateral ones. We show that if the input constrained triangular mesh has t triangles and its dual graph has h connected components, the resulting constrained quadrilateral mesh has at most $\lfloor\frac{3t}{2}\rfloor+4h$ quadrilaterals and at most t+3h Steiner points, one of which may be placed outside the triangular mesh domain. Examples of meshes generated by our algorithm, and an evaluation of the quality of these meshes with respect to a quadrilateral shape quality criterion are presented as well. [ABSTRACT FROM AUTHOR]

Given a set V of n points in a two-dimensional plane, we give an O(nlogn)-time centralized algorithm that constructs a planar t-spanner for V, for $t = \rho(\alpha) = \max\{\frac{\pi}{2}, \pi \sin \frac{\alpha}{2}+1\}\cdot C_{del}$ such that the degree of each node is bounded from above by $19 + \lceil \frac{2\pi}{\alpha} \rceil$, where 0<α<π/2 is an adjustable parameter. Here Cdel is the spanning ratio of the Delaunay triangulation, which is at most $\frac{4\sqrt{3}}{9}\pi$. We also show, by applying the greedy method in Ref. [14], how to construct a low weighted bounded degree planar spanner with spanning ratio ρ(α)2(1+∊) and the same degree bound, where ∊ is any positive real constant. Here, a structure is called low weighted if its total edge length is proportional to the total edge length of the Euclidean minimum spanning tree of V. Moreover, we show that our method can be extended to construct a planar bounded degree spanner for unit disk graphs with the adjustable parameter α satisfying 0<α<π/3. Previously, only centralized method6 of constructing bounded degree planar spanner is known, with degree bound 27 and spanning ratio t≃10.02. The distributed implementation of this centralized method takes O(n2) communications in the worst case. Our method can be converted to a localized algorithm where the total number of messages sent by all nodes is at most O(n). [ABSTRACT FROM AUTHOR]

Given a triangulation T of n points in the plane, we are interested in the minimal set of edges in T such that T can be reconstructed from this set (and the vertices of T) using constrained Delaunay triangulation. We show that this minimal set is precisely the set of non locally Delaunay edges, and that its cardinality is less than or equal to n + i/2 (if i is the number of interior points in T), which is a tight bound. [ABSTRACT FROM AUTHOR]

Given A-spline curves and A-patch surfaces that are implicitly defined on triangles and tetrahedra, we determine their NURBS representations. We provide a trimmed NURBS form for A-spline curves and a parametric tensor-product NURBS form for A-patch surfaces. We concentrate on cubic A-patches, providing a C¹-continuous surface that interpolates a given triangulation together with surface normals at the vertices. In many cases we can generate cubic trimming curves that are rationally parametrizable on the triangular faces of the tetrahedra; for the remaining faces we resort to using quadratic curves, which are always rationally parametrizable, to approximate the cubic trimming curves. [ABSTRACT FROM AUTHOR]

We generalize the operation of flipping an edge in a triangulation to that of flipping several edges simultaneously. Our main result is an optimal upper bound on the number of simultaneous flips that are needed to transform a triangulation into another. Our results hold for triangulations of point sets and for polygons. [ABSTRACT FROM AUTHOR]

Two recent methods have increased hopes of finding a polynomial time solution to the problem of computing the minimum weight triangulation of a set S of n points in the plane. Both involve computing what was believed to be a connected or nearly connected subgraph of the minimum weight triangulation, and then completing the triangulation optimally. The first method uses the light graph of S as its initial subgraph. The second method uses the LMT-skeleton of S. Both methods rely, for their polynomial time bound, on the initial subgraphs having only a constant number of components. Experiments performed by the authors of these methods seemed to confirm that randomly chosen point sets displayed this desired property. We show that there exist point sets where the number of components is linear in n. In fact, the expected number of components in either graph on a randomly chosen point set is linear in n, and the probability of the number of components exceeding some constant times n tends to one. [ABSTRACT FROM AUTHOR]

We propose algorithms to enumerate (1) regular triangulations, (2) spanning regular triangulations, (3) equivalence classes of regular triangulations with respect to symmetry, and (4) all triangulations. All of the algorithms are for arbitrary points in general dimension. They work in output-size sensitive time with memory only of several times the size of a triangulation. For the enumeration of regular triangulations, we use the fact by Gel'fand, Zelevinski&icaron; and Kapranov that regular triangulations correspond to the vertices of the secondary polytope. We use reverse search technique by Avis and Fukuda, its extension for enumerating equivalence classes of objects, and a reformulation of a maximal independent set enumeration algorithm. The last approach can be extended for enumeration of dissections. [ABSTRACT FROM AUTHOR]

We consider online routing algorithms for finding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no randomization, (2) no equivalent result is possible for convex subdivisions, (3) there is no competitive online routing algorithm under the Euclidean distance metric in arbitrary triangulations, and (4) there is no competitive online routing algorithm under the link distance metric even when the input graph is restricted to be a Delaunay, greedy, or minimum-weight triangulation. [ABSTRACT FROM AUTHOR]

This paper presents how the space of spheres and shelling may be used to delete a point from a d-dimensional triangulation efficiently. In dimension two, if k is the degree of the deleted vertex, the complexity is O(k log k), but we notice that this number only applies to low cost operations, while time consuming computations are only done a linear number of times. This algorithm may be viewed as a variation of Heller's algorithm,[sup 1,2] which is popular in the geographic information system community. Unfortunately, Heller algorithm is false, as explained in this paper. [ABSTRACT FROM AUTHOR]

The problem of computing a piecewise linear approximation to a surface from a set of sample points is important in solid modeling, computer graphics and computer vision. A recent algorithm using the Voronoi diagram of the sample points gave a guarantee on the distance of the output surface from the original sampled surface assuming that the sample was sufficiently dense. We give a similar algorithm, simplifying the computation and the proof of the geometric guarantee. In addition, we guarantee that our output surface is homeomorphic to the original surface; to our knowledge this is the first such topological guarantee for this problem. [ABSTRACT FROM AUTHOR]

A trip through a virtual world is a powerful metaphor and a natural way of interacting with a geographic information system (GIS). Virtual reality (VR) systems provide visual realism and real-time navigation and interaction for data in core, but fail to cope with very large amounts of data, and to provide the general functionality of information systems. We describe a prototype system that overcomes these problems by coupling two platforms: A client that runs the VR component interacts via a (local or wide area) network with a server that runs an object oriented database containing geographic data. For the purpose of accessing data efficiently, we describe how to integrate a geometric index into the database, and how to perform the operations that are requested in a real-time trip through the virtual world. [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]

This paper describes a new computational method of fully automated anisotropic triangulation of a trimmed parametric surface. Given as input: (1) a domain geometry and (2) a 3 × 3 tensor field that specifies a desired anisotropic node-spacing, this new approach first packs ellipsoids closely in the domain by defining proximity-based interacting forces among the ellipsoids and finding a force-balancing configuration using dynamic simulation. The centers of the ellipsoids are then connected by anisotropic Delaunay triangulation for a complete mesh topology. Since a specified tensor field controls the directions and the lengths of the ellipsoids' principal axes, the method generates a graded anisotropic mesh whose elements conform precisely to the given tensor field. [ABSTRACT FROM AUTHOR]

Open problems from the 15th Annual ACM Symposium on Computational Geometry. [ABSTRACT FROM AUTHOR]

We describe efficient PRAM algorithms for constructing unbalanced quadtrees, balanced quadtrees, and quadtree-based finite element meshes. Our algorithms take time O(log n) for point set input and O(log n log k) time for planar straight-line graphs, using O(n+k/log n) processors, where n measures input size and k output size. [ABSTRACT FROM AUTHOR]

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)[sup 2]) Steiner points and has running time O(n+(k+l)[sup 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(n[sup 2]) algorithm of Aronov, Seidel and Souvaine[sup 1] our algorithms are sensitive to the number of reflex vertices of the polygons. In particular, our algorithms have linear running time when k+l≤√n for the first algorithm, and kl≤n/log n for the second algorithm. [ABSTRACT FROM AUTHOR]

We give a result that implies an improvement by a factor of log log n in the hypercube bounds for the geometric problems of batched planar point location, trapezoidal decomposition, and polygon triangulation. The improvements are achieved through a better solution to the multisearch problem on a hypercube, a parallel search problem where the elements in the data structure S to be searched are totally ordered, but where it is not possible to compare in constant time any two given queries q and q′. Whereas the previous best solution to this problem took O(log n(log log n)[sup 3]) time on an n-processor hypercube, the solution given here takes O(log n(log log n)[sup 2]) time on an n-processor hypercube. The hypercube model for which we claim our bounds is the standard one, SIMD, with O(1) memory registers per processor, and with one-port communication. Each register can store O(log n) bits, so that a processor knows its ID. [ABSTRACT FROM AUTHOR]

The concept of pointed pseudo-triangulations is defined and a few of its applications described. [ABSTRACT FROM AUTHOR]