Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions

The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if S is a set of n points in general position in R ^d , the maximum complexity of its Voronoi diagram under the L _∞ metric, and also under a simplicial distance function, are both shown to be . The upper bound for the case of the L _∞ metric follows from a new upper bound, also proved in this paper, on the maximum complexity of the union of n axis-parallel hypercubes in R ^d . This complexity is , for d ≥ 1 , and it improves to , for d ≥ 2 , if all the hypercubes have the same size. Under the L ₁ metric, the maximum complexity of the Voronoi diagram of a set of n points in general position in R ³ is shown to be . We also show that the general position assumption is essential, and give examples where the complexity of the diagram increases significantly when the points are in degenerate configurations. (This increase does not occur with an appropriate modification of the diagram definition.) Finally, on-line algorithms are proposed for computing the Voronoi diagram of n points in R ^d under a simplicial or L _∞ distance function. Their expected randomized complexities are for simplicial diagrams and for L _∞ -diagrams. Received July 31, 1995, and in revised form September 9, 1997.     

Voronoi Diagrams and Convex Hulls of Random Moving Points

This report considers the expected combinatorial complexity of the Euclidean Voronoi diagram and the convex hull of sets of n independent random points moving in unit time between two positions drawn independently from the same distribution in R ^d for fixed d\ge 2 as n→∈fty . It is proved that, when the source and destination distributions are the uniform distribution on the unit d -ball, these complexities are Θ(n ^(d+1)/d ) for the Voronoi diagram and O(n ^(d-1)/(d+1) log n) for the convex hull. Additional results for the convex hull are O( log ^d n) for the uniform distribution in the unit d -cube and O( log ^(d+1)/2 n) for the d -dimensional normal distribution. Received November 23, 1998, and in revised form July 8, 1999.     

An optimal convex hull algorithm in any fixed dimension

We present a deterministic algorithm for computing the convex hull ofn points inE ^d in optimalO(n logn+n ^⌞d/2⌟ ) time. Optimal solutions were previously known only in even dimension and in dimension 3. A by-product of our result is an algorithm for computing the Voronoi diagram ofn points ind-space in optimalO(n logn+n ^⌜d/2⌝ ) time. This research was supported in part by the National Science Foundation under Grant CCR-9002352 and The Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc. A preliminary version of this paper has appeared in “An optimal convex hull algorithm and new results on cuttings”,Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science, October 1991, pp. 29–38. The convex hull algorithm given in the present paper, although similar in spirit, is considerably simpler than the one given in the proceedings.     

Voronoi diagrams of random lines and flats

It is proved that, for any fixedd ≽ 3 and 0 ≤k ≤ d - 1, the expected combinatorial complexity of the Euclidean Voronoi diagram ofn random &-flats drawn independently from the uniform distribution onk-flats intersecting the unit ball in ℝ^d is Ξ(n ^d/(d-k)) asn → ∞. A by-product of the proof is a density transformation for integrating over sets ofd + 1k-flats in ℝ^d     

Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions

The combinatorial complexity of the Voronoi diagram ofnlines in three dimensions under a convex distance function induced by a polytope with a constant number of edges is shown to beO(n²α(n)log n), where α(n) is a slowly growing inverse of the Ackermann function. There are arrangements ofnlines where this complexity can be as large as Ω(n²α(n)).     

Dynamic construction of abstract Voronoi diagrams

The abstract Voronoi diagram (AVD) introduced by R. Klein is a generalization of various concrete Voronoi diagrams—data structures actively used in the last decades for solving theoretical and practical geometric problems. This paper presents a fully dynamic algorithm for AVD construction based on Klein's incremental approach. It needs O(n) worst-case time for a new site insertion in an AVD with n sites. For the first time a possibility of effective site deletion without full reconstruction of AVD is proved. The proposed method for site deletion requires O(mn) expected time, where m is the number of invisible sites, and O(n) if invisible sites are not allowed. The dynamic algorithm consumes O(n) memory at any moment. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 2, pp. 133–146, 2007.     

A new duality result concerning voronoi diagrams

A new duality between order-k Voronoi diagrams inE ^d and convex hulls inE ^d+1 is established. It implies a reasonably simple algorithm for computing the order-k diagram forn points in the plane inO(k ² n logn) time and optimalO(k(n–k)) space.Research was supported by the Austrian Fond zur Foerderung der wissenschaftlichen Forschung.     

The Overlay of Minimization Diagrams in a Randomized Incremental Construction

In a randomized incremental construction of the minimization diagram of a collection of n hyperplanes in ℝ ^d , for d≥2, the hyperplanes are inserted one by one, in a random order, and the minimization diagram is updated after each insertion. We show that if we retain all the versions of the diagram, without removing any old feature that is now replaced by new features, the expected combinatorial complexity of the resulting overlay does not grow significantly. Specifically, this complexity is O(n ^⌊d/2⌋log n), for d odd, and O(n ^⌊d/2⌋), for d even. The bound is asymptotically tight in the worst case for d even, and we show that this is also the case for d=3. Several implications of this bound, mainly its relation to approximate halfspace range counting, are also discussed.     

On the construction of abstract voronoi diagrams

We show that the abstract Voronoi diagram ofn sites in the plane can be constructed in timeO(n logn) by a randomized algorithm. This yields an alternative, but simpler,O(n logn) algorithm in many previously considered cases and the firstO(n logn) algorithm in some cases, e.g., disjoint convex sites with the Euclidean distance function. Abstract Voronoi diagrams are given by a family of bisecting curves and were recently introduced by Klein [13]. Our algorithm is based on Clarkson and Shor's randomized incremental construction technique [7]. This work was supported by the DFG, Me 620/6, and ESPRIT P3075 ALCOM. A preliminary version of this paper has been presented at STACS '90, Rouen, France.     

An Optimal-Time Algorithm for Shortest Paths on a Convex Polytope in Three Dimensions

We present an optimal-time algorithm for computing (an implicit representation of) the shortest-path map from a fixed source s on the surface of a convex polytope P in three dimensions. Our algorithm runs in O(nlog n) time and requires O(nlog n) space, where n is the number of edges of P. The algorithm is based on the O(nlog n) algorithm of Hershberger and Suri for shortest paths in the plane (Hershberger, J., Suri, S. in SIAM J. Comput. 28(6):2215–2256, 1999), and similarly follows the continuous Dijkstra paradigm, which propagates a “wavefront” from s along ∂ P. This is effected by generalizing the concept of conforming subdivision of the free space introduced by Hershberger and Suri and by adapting it for the case of a convex polytope in ℝ³, allowing the algorithm to accomplish the propagation in discrete steps, between the “transparent” edges of the subdivision. The algorithm constructs a dynamic version of Mount’s data structure (Mount, D.M. in Discrete Comput. Geom. 2:153–174, 1987) that implicitly encodes the shortest paths from s to all other points of the surface. This structure allows us to answer single-source shortest-path queries, where the length of the path, as well as its combinatorial type, can be reported in O(log n) time; the actual path can be reported in additional O(k) time, where k is the number of polytope edges crossed by the path. The algorithm generalizes to the case of m source points to yield an implicit representation of the geodesic Voronoi diagram of m sites on the surface of P, in time O((n+m)log (n+m)), so that the site closest to a query point can be reported in time O(log (n+m)). Work on this paper was supported by NSF Grants CCR-00-98246 and CCF-05-14079, by a grant from the U.S.-Israeli Binational Science Foundation, by grant 155/05 from the Israel Science Fund, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. The paper is based on the Ph.D. Thesis of the first author, supervised by the second author. A preliminary version has been presented in Proc. 22nd Annu. ACM Sympos. Comput. Geom., pp. 30–39, 2006.     

Better lower bounds on detecting affine and spherical degeneracies

We show that in the worst case, Ω(n ^d ) sidedness queries are required to determine whether a set ofn points in ℝ ^d is affinely degenerate, i.e., whether it containsd+1 points on a common hyperplane. This matches known upper bounds. We give a straightforward adversary argument, based on the explicit construction of a point set containing Ω(n ^d ) “collapsible” simplices, any one of which can be made degenerate without changing the orientation of any other simplex. As an immediate corollary, we have an Ω(n ^d ) lower bound on the number of sidedness queries required to determine the order type of a set ofn points in ℝ ^d . Using similar techniques, we also show that Ω(n ^d+1) in-sphere queries are required to decide the existence of spherical degeneracies in a set ofn points in ℝ ^d . An earlier version of this paper was presented at the 34th Annual IEEE Symposium on Foundations of Computer Science [8]. This research has been supported by NSF Presidential Young Investigator Grant CCR-9058440.     

Piecewise linear paths among convex obstacles

Let ℬ be a set ofn arbitrary (possibly intersecting) convex obstacles in ℝ ^d . It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting ofO(n ^{(d−1)[d/2+1]}) segments. The bound cannot be improved below Ω(n ^d ); thus, in ℝ³, the answer is betweenn ³ andn ⁴. For open disjoint convex obstacles, a Θ(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case. This research was supported by The Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III Basic Research Action 6546 (PROMotion). J. M. acknowledges support by a Humboldt Research Fellowship. Part of this research was done while he visited Utrecht University.     

Distributed algorithms solving the updating problems

In this paper, we consider the updating problems to reconstruct the biconnected-components and to reconstruct the weighted shortest path in response to the topology change of the network. We propose two distributed algorithms. The first algorithm solves the updating problem that reconstructs the biconnected-components after the several processors and links are added and deleted. Its bit complexity is O((n′ +a +d) logn′), its message complexity is O(n′ +a +d), the ideal time complexity isO(n′), and the space complexity isO(e logn +e′ logn′). The second algorithm solves the updating problem that reconstructs the weighted shortest path. Its message complexity and ideal-time complexity areO(u ² +a +n′) respectively.     

Nonoverlap of the star unfolding

The star unfolding of a convex polytope with respect to a pointx on its surface is obtained by cutting the surface along the shortest paths fromx to every vertex, and flattening the surface on the plane. We establish two main properties of the star unfolding:

Upper bounds for the diameter and height of graphs of convex polyhedra

Let Δ(d, n) be the maximum diameter of the graph of ad-dimensional polyhedronP withn-facets. It was conjectured by Hirsch in 1957 that Δ(d, n) depends linearly onn andd. However, all known upper bounds for Δ(d, n) were exponential ind. We prove a quasi-polynomial bound Δ(d, n)≤n ^{2 logd+3}. LetP be ad-dimensional polyhedron withn facets, let ϕ be a linear objective function which is bounded onP and letv be a vertex ofP. We prove that in the graph ofP there exists a monotone path leading fromv to a vertex with maximal ϕ-value whose length is at most . This research was supported in part by a BSF grant, by a GIF grant, and by ONR-N00014-91-C0026.     

Farthest-polygon Voronoi diagrams

Given a family of k disjoint connected polygonal sites in general position and of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(nlog³n) time algorithm to compute it. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k−1 connected components, but if one component is bounded, then it is equal to the entire region.     

Kinetic Spanners in ℝ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

We present a new (1+ε)-spanner for sets of n points in ℝ ^d . Our spanner has size O(n/ε ^d−1) and maximum degree O(log  ^d n). The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming that the trajectories of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is O(n ²/ε ^d−1), and using a supporting data structure of size O(nlog  ^d n), we can handle events in time O(log  ^d+1 n). Moreover, the spanner can be updated in time O(log n) if the flight plan of a point changes. This is the first kinetic spanner for points in ℝ ^d whose performance does not depend on the spread of the point set.     

One-Sided Ideal Growth of Free Associative Algebras

Let R be a finitely generated associative algebra with unity over a finite field \Bbb F_q{\Bbb F}_q . Denote by a _n (R) the number of left ideals J ⊂ R such that dim R/J = n for all n ≥ 1. We explicitly compute and find asymptotics of the left ideal growth for the free associative algebra A _d of rank d with unity over \Bbb F_q{\Bbb F}_q , where d ≥ 1. This function yields a bound a _n (R) ≤ a _n (A _d ), n ? \Bbb Nn\in{\Bbb N} , where R is an arbitrary algebra generated by d elements. Denote by m _n (R) the number of maximal left ideals J ⊂ R such that dim R/J = n, for n ≥ 1. Let d ≥ 2, we prove that m _n (A _d ) ≈ a _n (A _d ) as n → ∞.     

Markov Jump Processes Approximating a Non-Symmetric Generalized Diffusion

Consider a non-symmetric generalized diffusion X(⋅) in ℝ ^d determined by the differential operator $A(\mbox{\boldmath{$A(\mbox{\boldmath{. In this paper the diffusion process is approximated by Markov jump processes X _n (⋅), in homogeneous and isotropic grids G _n ⊂ℝ ^d , which converge in distribution in the Skorokhod space D([0,∞),ℝ ^d ) to the diffusion X(⋅). The generators of X _n (⋅) are constructed explicitly. Due to the homogeneity and isotropy of grids, the proposed method for d≥3 can be applied to processes for which the diffusion tensor $\{a_{ij}(\mbox{\boldmath{$\{a_{ij}(\mbox{\boldmath{ fulfills an additional condition. The proposed construction offers a simple method for simulation of sample paths of non-symmetric generalized diffusion. Simulations are carried out in terms of jump processes X _n (⋅). For piece-wise constant functions a _ij on ℝ ^d and piece-wise continuous functions a _ij on ℝ² the construction and principal algorithm are described enabling an easy implementation into a computer code.     

Almost tight upper bounds for lower envelopes in higher dimensions

We consider the problem of bounding the combinatorial complexity of the lower envelope ofn surfaces or surface patches ind-space (d≥3), all algebraic of constant degree, and bounded by algebraic surfaces of constant degree. We show that the complexity of the lower envelope ofn such surface patches isO(n ^d−1+∈), for any ∈>0; the constant of proportionality depends on ∈, ond, ons, the maximum number of intersections among anyd-tuple of the given surfaces, and on the shape and degree of the surface patches and of their boundaries. This is the first nontrivial general upper bound for this problem, and it almost establishes a long-standing conjecture that the complexity of the envelope isO(n ^d-2λ _q (n)) for some constantq depending on the shape and degree of the surfaces (where λ _q (n) is the maximum length of (n, q) Davenport-Schinzel sequences). We also present a randomized algorithm for computing the envelope in three dimensions, with expected running timeO(n ^2+∈), and give several applications of the new bounds. Work on this paper has been supported by NSF Grant CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.