Search

We consider the problem of bounding the complexity of the k th level in an arrangement of n curves or surfaces, a problem dual to, and an extension of, the well-known k-set problem. Among other results, we prove a new bound, O(nk 5/3 ) , on the complexity of the k th level in an arrangement of n planes in R 3 , or on the number of k -sets in a set of n points in three dimensions, and we show that the complexity of the k th level in an arrangement of n line segments in the plane is \(O(n\sqrt{k}\alpha(n/k))\) , and that the complexity of the k th level in an arrangement of n triangles in 3-space is O(n 2 k 5/6 α(n/k)) . 26 June, 1998 Editors-in-Chief: la href=../edboard.html#chiefslJacob E. Goodman, Richard Pollackl/al 19n3p315.pdf yes no no yes

Let F be a collection of n d-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices, edges, and 2-faces of the lower envelope (i.e., pointwise minimum) of F in expected time O(nd+ϵ), for any ϵ>0. For d=3, by combining this algorithm with the point location technique of Preparata and Tamassia, we can compute, in randomized expected time O(n3+ϵ) for any ϵ>0, a data structure of size O(n3+ϵ) that, given any query point q, can determine in O(log2n) time whether q lies above, below or on the envelope. As a consequence, we obtain improved algorithmic solutions to many problems in computational geometry, including (a) computing the width of a point set in 3-space, (b) computing the biggest stick in a simple polygon in the plane, and (c) computing the smallest-width annulus covering a planar point set. The solutions to these problems run in time O(n17/11+ϵ), for any ϵ>0 improving previous solutions that run in time O(n8/5+ϵ). We also present data structures for (i) performing nearest-neighbor and related queries for fairly general collections of objects in 3-space and for collections of moving objects in the plane, and (ii) performing ray-shooting and related queries among n spheres or more general objects in 3-space. Both of these data structures require O(n3+ϵ) storage and preprocessing time, for any ϵ>0, and support polylogarithmic-time queries. These structures improve previous solutions to these problems.

We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graph G, a family G={G1,G2,...,Gk} is called a clique cover of G if (i) each Gi is a clique or a bipartite clique, and (ii) the union of Gi is G. The size of the clique cover G is defined as Σki=1 ni, where ni is the number of vertices in Gi. Our main result is that there exist visibility graphs of n nonintersecting line segments in the plane whose smallest clique cover has size Ω(n2/log2n. An upper bound of 0(n2/log n) on the clique cover follows from a well-known result in extremal graph theory. On the other hand, we show that the visibility graph of a simple polygon always admits a clique cover of size O(n log3 n), and that there are simple polygons whose visibility graphs require a clique cover of size Ω(n log n).

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:1.It does not self-overlap: it is a simple polygon.2.The ridge tree in the unfolding, which is the locus of points with more than one shortest path fromx, is precisely the Voronoi diagram of the images ofx, restricted to the unfolding. These two properties permit conceptual simplification of several algorithms concerned with shortest paths on polytopes, and sometimes a worst-case complexity improvement as well:?The construction of the ridge tree (in preparation for shortest-path queries, for instance) can be achieved by an especially simpleO(n2) algorithm. This is no worst-case complexity improvement, but a considerable simplification nonetheless.?The exact set of all shortest-path "edge sequences" on a polytope can be found by an algorithm considerably simpler than was known previously, with a time improvement of roughly a factor ofn over the old bound ofO(n7 logn).?The geodesic diameter of a polygon can be found inO(n9 logn) time, an improvement of the previous bestO(n10) algorithm. Our results suggest conjectures on "unfoldings" of general convex surfaces.

We describe a randomized algorithm for computing the kth smallest distance in a set of n points in the plane, based on the parametric search technique of Megiddo [Me1]. The expected running time of our algorithm is O(n4/3 log 8/3 n). A deterministic version of our procedure runs in time O(n3/2 log5/2 n). Both versions improve the previously best known upper bound of O(n9/5 log4/5 n) by Chazelle [Ch]. A simple O(n log n) time algorithm for computing an approximation of the median distance is also presented.