Search

It has been suggested in the literature that ordinary finite-precision floating-point arithmetic is inadequate for geometric computation, and that researchers in numerical analysis may believe that the difficulties of error in geometric computation can be overcome by simple approaches. It is the purpose of this paper to show that these suggestions, based on an example showing failure of a certain algorithm for computing planar convex hulls, are misleading, and why this is so. It is first shown how the now-classical backward error analysis can be applied in the area of computational geometry. This analysis is relevant in the context of uncertain data, which may well be the practical context for computational-geometry algorithms such as, say, those for computing convex hulls. The exposition will illustrate the fact that the backward error analysis does not pretend to overcome the problem of finite precision: it merely provides a way to distinguish those algorithms that overcome the problem to whatever extent it is possible to do so. It is then shown that often the situation in computational geometry is exactly parallel to other areas, such as the numerical solution of linear equations, or the algebraic eigenvalue problem. Indeed, the example mentioned can be viewed simply as an example of the use of an unstable algorithm, for a problem for which computational geometry has already discovered provably stable algorithms. Finally, the paper discusses the implications of these analyses for applications in three-dimensional solid modeling. This is done by considering a problem defined in terms of a simple extension of the planar convex-hull algorithm, namely, the verification of the well-formedness of extruded objects. A brief discussion concerning more difficult problems in solid modeling is also included. [ABSTRACT FROM AUTHOR]

This paper studies the two-dimensional range search problem, and constructs a simple and efficient algorithm based on the Voronoi diagram. In this problem, a set of points and a query range are given, and we want to enumerate all the points which are inside the query range as quickly as possible. In most of the previous researches on this problem, the shape of the query range is restricted to particular ones such as circles, rectangles and triangles, and the improvement on the worst-case performance has been pursued. On the other hand, the algorithm proposed in this paper is designed for a general shape of the query range in the two-dimensional space, and is intended to accomplish a good average-case performance. This performance is actually observed by numerical experiments. In these experiments, we compare the execution time of the proposed algorithm with those of other representative algorithms such as those based on the bucketing technique and the k-d tree. We can observe that our algorithm shows the better performance in almost all the cases. [ABSTRACT FROM AUTHOR]

There is strong empirical evidence that human perception of a graph drawing is negatively correlated with the number of edge crossings. However, recent experiments show that one can reduce the negative effect by ensuring that the edges that cross do so at large angles. These experiments have motivated a number of mathematical and algorithmic studies of 'right angle crossing (RAC)' drawings of graphs, where the edges cross each other perpendicularly. In this paper we give an algorithm for constructing RAC drawings of 'outer-1-plane' graphs, that is, topological graphs in which each vertex appears on the outer face, and each edge crosses at most one other edge. The drawing algorithm preserves the embedding of the input graph. This is one of the few algorithms available to construct RAC drawings. [ABSTRACT FROM AUTHOR]

This paper starts the investigation of a constrained version of the point-set embed-dability problem. Let G = (V,E) be a planar graph with n vertices, G′ = (V′,E′) a subgraph of G, and S a set of n distinct points in the plane. We study the problem of computing a point-set embedding of G on S subject to the constraint that G′ is drawn with straight-line edges. Different drawing algorithms are presented that guarantee small curve complexity of the resulting drawing, i.e. a small number of bends per edge. It is proved that: • If G′ is an outerplanar graph and S is any set of points in convex position, a point-set embedding of G on S can be computed such that the edges of E\E′ have at most 4 bends each. • If S is any set of points in general position and G′ is a face of G or if it is a simple path, the curve complexity of the edges of E\E′ is at most 8. • If S is in general position and G′ is a set of k disjoint paths, the curve complexity of the edges of E \ E′ is O(2k). [ABSTRACT FROM AUTHOR]

We study optimization problems for polyhedral terrains in the presence of data imprecision. An imprecise terrain is given by a triangulated point set where the height component of the vertices is specified by an interval of possible values. We restrict ourselves to terrains with a one-dimensional projection, usually referred to as 1.5-dimensional terrains, where an imprecise terrain is given by an x-monotone polyline, and the y-coordinate of each vertex is not fixed but only constrained to a given interval. Motivated mainly by applications in terrain analysis, in this paper we study five different optimization measures related to obtaining smooth terrains, for the 1.5-dimensional case. In particular, we present exact algorithms to minimize and maximize the total turning angle, as well as to minimize the maximum slope change. Furthermore, we also give approximation algorithms to minimize the largest turning angle and to maximize the smallest turning angle. [ABSTRACT FROM AUTHOR]

We implement an algorithm for k-clustering for small k in fixed dimensions and report experimental results here. Although the theoretical bounds on the running time are hopeless for 1 + ∊ approximating k-clusters, we note that for dimensions 2 and 3, k-clustering is practical for small k (k ≤ 4) and simple enough shapes. For the purposes of this paper, k is a small fixed constant. [ABSTRACT FROM AUTHOR]

Geometric spanner is a fundamental structure in computational geometry and plays an important role in many geometric networks design applications. In this paper, we consider a generalization of the classical geometric spanner problem (called segment spanner): Given a set S of n disjoint 2-D segments, find a spanning network GS with minimum size so that for any pair of points in S, there exists a path in GS with length no more than t times their Euclidean distance. Based on a number of interesting techniques (such as weakly dominating set, strongly dominating set, interval cover, and imaginary Steiner points), we present an efficient algorithm to construct the segment spanner. Our approach first identifies a set Q of Steiner points in S and then constructs a point spanner for the set of Steiner points. Our algorithm runs in O(|Q| + n2log n) time and Q is a constant approximation (in terms of its size) of the optimal solution when S has a constant relative separation ratio. The approximation ratio depends on the stretch factor t and the relative separation ratio of S. [ABSTRACT FROM AUTHOR]

Consider a geometric network G in the plane. The dilation between any two vertices x and y in G is the ratio of the shortest path distance between x and y in G to the Euclidean distance between them. The maximum dilation over all pairs of vertices in G is called the dilation of G. In this paper, a randomized algorithm is presented which, when given a polygonal cycle C on n vertices in the plane, computes in O(n log3 n) expected time, the edge of C whose removal results in a polygonal path of smallest possible dilation. It is also shown that the edge whose removal gives a polygonal path of largest possible dilation can be computed in O(n log n) time. If C is a convex polygon, the running time for the latter problem becomes O(n). Finally, it is shown that a (1 - ϵ)-approximation to the dilation of every path C \{e}, for all edges e of C, can be computed in O(n log n) total time. [ABSTRACT FROM AUTHOR]

Two points a and b are said to be L-visible among a set of polygonal obstacles if the length of the shortest path from a to b avoiding these obstacles is no more than L. For a given convex polygon P with n vertices, Gewali et al.1 addressed the guard placement problem on the boundary of P that covers the maximum area outside to the polygon under L-visibility with P as obstacle. Their proposed algorithm runs in O(n) time if $L\, < \,{{\pi (P)} \over 2}$, where π(P) denotes the perimeter of P. They conjectured that if $L\, \ge \,{{\pi (P)} \over 2}$, then the problem can be solved in subquadratic time. In this paper, we settle the conjecture in the affirmative sense, by proposing an easy to implement linear time algorithm for any arbitrary value of L. [ABSTRACT FROM AUTHOR]

In Part I, we described an efficient and robust algorithm for computing a common refinement of two surface meshes. In this paper, we present a theoretical verification of the robustness of our algorithm by showing the topological preservation of the intersection principle, which we used to resolve topological inconsistencies caused by numerical errors. To enhance robustness in practice for complex geometries, we further propose techniques to detect and match geometric features, such as ridges, corners, and nonmatching boundaries. We report experimental results using our enhanced overlay algorithm with feature matching for complex geometries from real-world applications. [ABSTRACT FROM AUTHOR]