Splitting a Delaunay Triangulation in Linear Time

Abstract. Computing the Delaunay triangulation of n points requires usually a minimum of Ω(n log n) operations, but in some special cases where some additional knowledge is provided, faster algorithms can be designed. Given two sets of points, we prove that, if the Delaunay triangulation of all the points is known, the Delaunay triangulation of each set can be computed in randomized expected linear time.     

Monochromatic geometric k-factors for bicolored point sets with auxiliary points

Given a bicolored point set S, it is not always possible to construct a monochromatic geometric planar k-factor of S. We consider the problem of finding such a k-factor of S by using auxiliary points. Two types are considered: white points whose position is fixed, and Steiner points which have no fixed position. Our approach provides algorithms for constructing those k-factors, and gives bounds on the number of auxiliary points needed to draw a monochromatic geometric planar k-factor of S.     

Algorithms for computing the center of area of a convex polygon

The center of area of a convex polygonP is the unique pointp ^* that maximizes the minimum area overlap betweenP and any halfplane that includesp ^*. We show thatp ^* is unique and present two algorithms for its computation. The first is a combinatorial algorithm that runs in timeO (n ⁶ log² n). The second is a numerical algorithm that runs in timeO(GK(n+K)) whereK represents the number of desired bits of precision in the output coordinates andG the number of bits used to represent the coordinates of the input polygon vertices. We conclude with a discussion of implementation issues and related results.Research partially supported by the second author's NSF grant CCR-8351468, at Johns Hopkins University and Smith College.     

Generation of configuration space obstacles: The case of moving algebraic curves

We present algebraic algorithms to generate the boundary of planar configuration space obstacles arising from the translatory motion of objects among obstacles. Both the boundaries of the objects and obstacles are given by segments of algebraic plane curves.Research supported in part by NSF Grant MIP-85-21356 and a David Ross Fellowship. An earlier version of this paper appeared in theProceedings of the 1987 IEEE International Conference on Robotics and Automation, pp. 979–984.     

An optimal algorithm for the boundary of a cell in a union of rays

In this paper we study a cell of the subdivision induced by a union ofn half-lines (or rays) in the plane. We present two results. The first one is a novel proof of theO(n) bound on the number of edges of the boundary of such a cell, which is essentially of methodological interest. The second is an algorithm for constructing the boundary of any cell, which runs in optimal (n logn) time. A by-product of our results are the notions of skeleton and of skeletal order, which may be of interest in their own right.This work was partly supported by CEE ESPRIT Project P-940, by the Ecole Normale Supérieure, Paris, and by NSF Grant ECS-84-10902.This work was done in part while this author was visiting the Ecole Normale Supérieure, Paris, France.     

Fast computation of smallest enclosing circle with center on a query line segment

Here we propose an efficient algorithm for computing the smallest enclosing circle whose center is constrained to lie on a query line segment. Our algorithm preprocesses a given set of n points P={p₁,p₂,…,pn} such that for any query line or line segment L, it efficiently locates a point c on L that minimizes the maximum distance among the points in P from c. Roy et al. [S. Roy, A. Karmakar, S. Das, S.C. Nandy, Constrained minimum enclosing circle with center on a query line segment, in: Proc. of the 31st Mathematical Foundation of Computer Science, 2006, pp. 765-776] have proposed an algorithm that solves the query problem in O(log²n) time using O(nlogn) preprocessing time and O(n) space. Our algorithm improves the query time to O(logn); but the preprocessing time and space complexities are both O(n²).     

Quasi-optimal upper bounds for simplex range searching and new zone theorems

This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ^d so that, given any query simplexq, the points inP q can be counted or reported efficiently. Ifm units of storage are available (n <m <n ^d ), then we show that it is possible to answer any query inO(n ¹⁺/m ^1/d ) query time afterO(m ¹⁺) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n ^d+) storage for any fixed > 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.A preliminary version of this paper has appeared in theProceedings of the Sixth Annual ACM Symposium on Computational Geometry, June 1990, pp. 23–33. Work on this paper by Bernard Chazelle has been supported by NSF Grant CCR-87-00917 and NSF Grant CCR-90-02352. Work on this paper by Micha Sharir has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-8901484, and by grants from the U.S.-Israeli Binational Science Foundation, the NCRD—the Israeli National Council for Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences. Work by Emo Welzl has been supported by Deutsche Forschungsgemeinschaft Grant We 1265/1–2. Micha Sharir and Emo Welzl have also been supported by a grant from the German-Israeli Binational Science Foundation. Last but not least, all authors thank DIMACS, an NSF Science and Technology Center, for additional support under Grant STC-88-09648.     

An optimal speed-up parallel algorithm for triangulating simplicial point sets in space

Previous research on developing parallel triangulation algorithms concentrated on triangulating planar point sets.O(log³ n) running time algorithms usingO(n) processors have been developed in Refs. 1 and 2. Atallah and Goodrich⁽³⁾ presented a data structure that can be viewed as a parallel analogue of the sequential plane-sweeping paradigm, which can be used to triangulate a planar point set inO(logn loglogn) time usingO(n) processors. Recently Merks⁽⁴⁾ described an algorithm for triangulating point sets which runs inO(logn) time usingO(n) processors, and is thus optimal. In this paper we develop a parallel algorithm for triangulating simplicial point sets in arbitrary dimensions based on the idea of the sequential algorithm presented in Ref. 5. The algorithm runs inO(log² n) time usingO(n/logn) processors. The algorithm hasO(n logn) as the product of the running time and the number of processors; i.e., an optimal speed-up.     

An algorithm for computing the restriction scaffold assignment problem in computational biology

Let S and T be two finite sets of points on the real line with |S|+|T|=n and |S|>|T|. The restriction scaffold assignment problem in computational biology assigns each point of S to a point of T such that the sum of all the assignment costs is minimized, with the constraint that every element of T must be assigned at least one element of S. The cost of assigning an element si of S to an element tj of T is |si−tj|, i.e., the distance between si and tj. In 2003 Ben-Dor, Karp, Schwikowski and Shamir [J. Comput. Biol. 10 (2) (2003) 385] published an O(nlogn) time algorithm for this problem. Here we provide a counterexample to their algorithm and present a new algorithm that runs in O(n²) time, improving the best previous complexity of O(n³).     

Applying the improved Chen and Han’s algorithm to different versions of shortest path problems on a polyhedral surface

The computation of shortest paths on a polyhedral surface is a common operation in many computer graphics applications. There are two best known exact algorithms for the “single source, any destination” shortest path problem. One is proposed by Mitchell et al. (1987) [1]. The other is by Chen and Han (1990) [11]. Recently, Xin and Wang (2009) [9] improved the CH algorithm by exploiting a filtering theorem and achieved a practical method that outperforms both the CH algorithm and the MMP algorithm whether in time or in space.In this paper, we apply the improved CH algorithm to different versions of shortest path problems. The contributions of this paper include: (1) For a surface point p∈△v₁v₂v₃, we present an unfolding technique for estimating the distance value at p using the distances at v₁,v₂ and v₃. (2) We show that the improved CH algorithm can be naturally extended to the “multiple sources, any destination” version. Also, introducing a well-chosen heuristic factor into the improved CH algorithm will induce an exact solution to the “single source, single destination” version. (3) At the conclusion of multi-source shortest path algorithms, we can use the distance values at vertices to approximately compute the geodesic-distance-based offsets, the Voronoi diagram and the Delaunay triangulation in O(n) time. (4) By importing a precision parameter λ, we obtain a precision controlled approximant which varies from the improved CH algorithm to Dijkstra’s algorithm as λ increases from 0 to 1. Thus, an interesting relationship between them can be naturally established.     

Tractability frontiers of the partner units configuration problem

The partner units problem (PUP) is an acknowledged hard benchmark problem for the Logic Programming community with various industrial application fields like surveillance, electrical engineering, computer networks or railway safety systems. Although it is already known for a while that the PUP is NP-complete in its general form, complexity for subproblems reflecting the real problems in industrial fields remained widely unclear so far. In this article we provide all missing complexity results. For the subclass of the PUP that belongs to the complexity class P we present a polynomial-time algorithm and give in-depth algorithmic complexity results.     

Finding extreme points in three dimensions and solving the post-office problem in the plane

This paper describes an optimal solution for the following geometric search problem defined for a set P of n points in three dimensions: Given a plane h with all points of P on one side and a line ? in h, determine a point of P that is hit first when h is rotated around ?. The solution takes O(n) space and O(log n) time for a query. By use of geometric transforms, the post-office problem for a finite set of points in two dimensions and certain two-dimensional point location problems are reduced to the former problem and thus also optimally solved.     

Staircase visibility and computation of kernels

Let be some set of orientations, that is, . We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in . We call such curves -staircases. Two points p andq in a polygonP are said to -see each other if an -staircase fromp toq exists that is completely contained inP. The -kernel of a polygonP is then the set of all points which -see all other points. The -kernel of a simple polygon can be obtained as the intersection of all {}-kernels, with . With the help of this observation we are able to develop an algorithm to compute the -kernel of a simple polygon, for finite . We also show how to compute theexternal -kernel of a polygon in optimal time . The two algorithms are combined to compute the ( -kernel of a polygon with holes in time .This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/5-4 and the Natural Sciences and Engineering Research Council of Canada and Information Technology Research Centre of Ontario.     

A new algorithm for the largest empty rectangle problem

A rectangleA and a setS ofn points inA are given. We present a new simple algorithm for the so-called largest empty rectangle problem, i.e., the problem of finding a maximum area rectangle contained inA and not containing any point ofS in its interior. The computational complexity of the presented algorithm isO(n logn + s), where s is the number of possible restricted rectangles considered. Moreover, the expected performance isO(n · logn).     

Ray Coherence Between a Sphere and a Convex Polyhedron

Using the two ray coherence theorems of Ohta and Maekawa the computation time of ray tracing algorithms for scenes of spheres and convex polyhedra can be reduced considerably. This paper presents further theorems which, together with the first two, may enable further reduction in computation time.     

Base station placement on boundary of a convex polygon

Let P be a polygonal region which is forbidden for placing a base station in the context of mobile communication. Our objective is to place one base station at any point on the boundary of P and assign a range such that every point in the region is covered by that base station and the range assigned to that base station for covering the region is minimum among all such possible choices of base stations. Here we consider the forbidden region P as convex and base station can be placed on the boundary of the region. We present optimum linear time algorithm for that problem. In addition, we propose a linear time algorithm for placing a pair of base stations on a specified side of the boundary such that the range assigned to those base stations in order to cover the region is minimum among all such possible choices of a pair of base stations on that side.     

Using geometry to solve the transportation problem in the plane

LetU andV be two sets of points in the plane, where ¦U¦=k,¦V¦=, andn=k+. These two sets of points induce a directed complete bipartite graph in which the points represent nodes and an edge is directed from each node inU to each node in K Each edge is given a cost equal to the distance between the corresponding nodes measured by some metricd on the plane. We consider thetransportation problem on such a graph. We present an 0(n^2,5 logn logN) algorithm, whereN is the magnitude of the largest supply or demand. The algorithm uses some fundamental results of computational geometry and scaling of supplies and demands. The algorithm is valid for the ₁ metric, the ₂ metric, and the metric. The running time for the ₁ and metrics can be improved to 0(n²(logn)³ logN).D. S. Atkinson was supported by the National Science Foundation under Grant CCR90-57481PYI. P. M. Vaidya was supported by the National Science Foundation under Grants CCR-9057481 and CCR-9007195.     

Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems

In this paper we introduce a new technique for approximation schemes for geometrical optimization problems. As an example problem, we consider the following variant of the geometric Steiner tree problem. Every point u which is not included in the tree costs a penalty of π(u) units. Furthermore, every Steiner point that we use costs c _S units. The goal is to minimize the total length of the tree plus the penalties. Our technique yields a polynomial time approximation scheme for the problem, if the points lie in the plane. A preliminary version of this paper appeared in the Proceedings of the 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2005, 221–232.