Kinetic collision detection with fast flight plan changes

We show how to augment a kinetic data structure for collision detection between translating polygons with the ability to make fast flight plan changes. This allows us to update the KDS after a moving polygon changes its motion in O(logn) time, instead of the Ω(n) worst-case time needed by previous kinetic data structures. The key to our approach is replacing the KDS priority queue by a dynamic convex hull that represents the certificates of the KDS.     

Dynamic Connectivity for Axis-Parallel Rectangles

In this paper we give a fully dynamic data structure to maintain the connectivity of the intersection graph of n axis-parallel rectangles. The amortized update time (insertion and deletion of rectangles) is and the query time (deciding whether two given rectangles are connected) is O(1). It slightly improves the update time (O(n ^0.94)) of the previous method while drastically reducing the query time (near O(n ^1/3)). In addition, our method does not use fast matrix multiplication results and supports a wider range of queries. This work has been supported by an NSERC grant.     

Parallel computational geometry

We present efficient parallel algorithms for several basic problems in computational geometry: convex hulls, Voronoi diagrams, detecting line segment intersections, triangulating simple polygons, minimizing a circumscribing triangle, and recursive data-structures for three-dimensional queries.The work of C. Ó'Dúnlaing and C. Yap was supported by NSF Grants DCR-84-01898 and DCR-84-01633.     

Performance analysis of partial-match search algorithms for BD trees

Database systems are becoming increasingly popular for answering queries. Partial-match search queries are an important class of queries in such a system. Several storage structures have been proposed to answer these queries efficiently. The BD tree is an example of such a storage structure. A previous study indicated that the k-d tree performance is better than that of the BD tree for partial-match search queries. A recent paper reported some improved algorithms. However, it is unclear whether the improved algorithms show the BD tree in a favourable light for partial-match search queries. This paper explores the performance of these algorithms and compares their performance to that of the k-d tree. Since the BD tree construction process uses some heuristics to make it a better balanced tree, this paper also evaluates the effect of these heuristics on the partial-match search algorithms. The major conclusions of this study are that the BD tree performance for partial-match search is better than that of the k-d tree when an improved algorithm is used for partial-match search, and only the DZ expression rearrangement heuristic has substantial effect on partial-match search performance.     

Fast heuristic algorithms for rectilinear steiner trees

A fundamental problem in circuit design is how to connectn points in the plane, to make them electrically common using the least amount of wire. The tree formed, a Steiner tree, is usually constructed with respect to the rectilinear metric. The problem is known to be NP-complete; an extensive review of proposed heuristics is given. An early algorithm by Hanan is shown to have anO(n logn) time implementation using computational geometry techniques. The algorithm can be modified to do sequential searching inO(n ²) total time. However, it is shown that the latter approach runs inO(n ^3/2) expected time, forn points selected from anm×m grid. Empirical results are presented for problems up to 10,000 points.     

Convex hulls of objects bounded by algebraic curves

We present an0(n ·d ^o(1)) algorithm to compute the convex hull of a curved object bounded by0(n) algebraic curve segments of maximum degreed.Research supported in part by NSF Grant MIP-85 21356, ARO Contract DAA G29-85-C0018 under Cornell MSI, and ONR Contract N00014-88-K-0402. This paper is an updated version of a part of [6].     

Primitives for the manipulation of three-dimensional subdivisions

Algorithms for manipulating three-dimensional cell complexes are seldom implemented due to the lack of a suitable data structure for representing them. Such a data structure is proposed here along with the primitive operations necessary to make it useful. Applications of the structure are also given.This work was supported in part by the National Science Foundation under Grant No. DCR85-05517.     

Kinetic Collision Detection for Convex Fat Objects

We design compact and responsive kinetic data structures for detecting collisions between n convex fat objects in 3-dimensional space that can have arbitrary sizes. Our main results are:

Translation separability of sets of polygons

We consider the problem of separating a set of polygons by a sequence of translations (one such collision-free translation motion for each polygon). If all translations are performed in a common direction the separability problem so obtained has been referred to as the uni-directional separability problem; for different translation directions, the more general multi-directional separability problem arises. The class of such separability problems has been studied previously and arises e.g. in computer graphics and robotics. Existing solutions to the uni-directional problem typically assume the objects to have a certain predetermined shape (e.g., rectangular or convex objects), or to have a direction of separation already available. Here we show how to compute all directions of unidirectional separability for sets of arbitrary simple polygons.The problem of determining whether a set of polygons is multi-directionally separable had been posed by G.T. Toussaint. Here we present an algorithm for solving this problem which, in addition to detecting whether or not the given set is multidirectionally separable, also provides an ordering in which to separate the polygons. In case that the entire set is not multi-directionally separable, the algorithm will find the largest separable subset.Research supported by NSERC under grant No. A9173 and A0392, respectively     

Efficient selection, storage, and retrieval of irregularly distributed elevation data

The advantages and disadvantages of various digital terrain models are discussed briefly and a new model for triangulating a set of nonuniformly distributed three-dimensional surface observations is described. An algorithm for hierarchical subdivision of a set of data points into nested triangles is proposed. The algorithm selects a subset of the data points which reduce the maximum error between a piecewise linear approximation of the surface using only the selected points and the elevations of the points not selected. The data structure used is such that for any given degree of approximation (in the maximum-error sense) only the necessary points need to be stored. Furthermore, an efficient method is available to approximate the elevation of the surface at any point not included in the original data. The performance of the algorithm is demonstrated experimentally.     

A new approach on indexing mobile objects on the plane

We present a set of time-efficient approaches to index objects moving on the plane to efficiently answer range queries about their future positions. Our algorithms are based on previously described solutions as well as on the employment of efficient access methods. Finally, an experimental evaluation is included that shows the performance, scalability and efficiency of our methods.     

Reporting Red—Blue Intersections between Two Sets of Connected Line Segments

Abstract. We present a new line sweep algorithm, HEAPSWEEP, for reporting bichromatic (``purple') intersections between a red and a blue family of line segments. If the union of the segments in each family is connected as a point set, HEAPSWEEP reports all k purple intersections in time O((n+k) α(n) log ³ n) , where n is the total number of input segments and α(n) is the nearly constant inverse Ackermann function. To achieve these bounds, the algorithm maintains only partial information about the vertical ordering between curves of the same color, using a new data structure called a kinetic queue . In order to analyze the running time of HEAPSWEEP, we also show that a simple polygon containing a set of n line segments can be partitioned into monotone regions by a set of vertical threads cutting these segments O(n log n) times.     

Space Efficient Dynamic Orthogonal Range Reporting

In this paper we present new space efficient dynamic data structures for orthogonal range reporting. The described data structures support planar range reporting queries in time O(log n+klog log (4n/(k+1))) and space O(nlog log n), or in time O(log n+k) and space O(nlog  ^ε n) for any ε>0. Both data structures can be constructed in O(nlog n) time and support insert and delete operations in amortized time O(log ² n) and O(log nlog log n) respectively. These results match the corresponding upper space bounds of Chazelle (SIAM J. Comput. 17, 427–462, 1988) for the static case. We also present a dynamic data structure for d-dimensional range reporting with search time O(log  ^d−1 n+k), update time O(log  ^d n), and space O(nlog  ^d−2+ε n) for any ε>0. The model of computation used in our paper is a unit cost RAM with word size log n. A preliminary version of this paper appeared in the Proceedings of the 21st Annual ACM Symposium on Computational Geometry 2005. Work partially supported by IST grant 14036 (RAND-APX).     

Approximation algorithms for terrain guarding

We present approximation algorithms and heuristics for several variations of terrain guarding problems, where we need to guard a terrain in its entirety by a minimum number of guards. Terrain guarding has applications in telecommunications, namely in the setting up of antenna networks for wireless communication. Our approximation algorithms transform the terrain guarding instance into a Minimum Set Cover instance, which is then solved by the standard greedy approximation algorithm [J. Comput. System Sci. 9 (1974) 256-278]. The approximation algorithms achieve approximation ratios of O(logn), where n is the number of vertices in the input terrain. We also briefly discuss some heuristic approaches for solving other variations of terrain guarding problems, for which no approximation algorithms are known. These heuristic approaches do not guarantee non-trivial approximation ratios but may still yield good solutions.     

Transforming spanning trees and pseudo-triangulations

Let TS be the set of all crossing-free straight line spanning trees of a planar n-point set S. Consider the graph TS where two members T and T^′ of TS are adjacent if T intersects T^′ only in points of S or in common edges. We prove that the diameter of TS is O(logk), where k denotes the number of convex layers of S. Based on this result, we show that the flip graph PS of pseudo-triangulations of S (where two pseudo-triangulations are adjacent if they differ in exactly one edge—either by replacement or by removal) has a diameter of O(nlogk). This sharpens a known O(nlogn) bound. Let be the induced subgraph of pointed pseudo-triangulations of PS. We present an example showing that the distance between two nodes in is strictly larger than the distance between the corresponding nodes in PS.     

Randomized splay trees: Theoretical and experimental results

Splay trees are self-organizing binary search trees that were introduced by Sleator and Tarjan [J. ACM 32 (1985) 652-686]. In this paper we present a randomized variant of these trees. The new algorithm for reorganizing the tree is both simple and easy to implement. We prove that our randomized splaying scheme has the same asymptotic performance as the original deterministic scheme but improves constants in the expected running time. This is interesting in practice because the search time in splay trees is typically higher than the search time in skip lists and AVL-trees. We present a detailed experimental study of our algorithm. On request sequences generated by fixed probability distributions, we can achieve improvements of up to 25% over deterministic splaying. On request sequences that exhibit high locality of reference, the improvements are minor.     

Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines

We develop efficient algorithms for a number of generalized intersection reporting problems, including orthogonal and general segment intersection, 2D range searching, rectangular point enclosure, and rectangle intersection search. Our results for orthogonal and general segment intersection, 3-sided 2D range searching, and rectangular pointer enclosure problems match the lower bounds for their corresponding standard versions under the pointer machine model. Our results for the remaining problems improve upon the best known previous algorithms.     

Parallel methods for visibility and shortest-path problems in simple polygons

In this paper we give efficient parallel algorithms for solving a number of visibility and shortest-path problems for simple polygons. Our algorithms all run inO(logn) time and are based on the use of a new data structure for implicitly representing all shortest paths in a simple polygonP, which we call thestratified decomposition tree. We use this approach to derive efficient parallel methods for computing the visibility ofP from an edge, constructing the visibility graph of the vertices ofP (using an output-sensitive number of processors), constructing the shortest-path tree from a vertex ofP, and determining all-farthest neighbors for the vertices inP. The computational model we use is the CREW PRAM.This research was announced in preliminary form in theProceedings of the 6th ACM Symposium on Computational Geometry, 1990, pp. 73–82. The research of Michael T. Goodrich was supported by the National Science Foundation under Grants CCR-8810568 and CCR-9003299, and by the NSF and DARPA under Grant CCR-8908092.