SOCG

We prove that, for any constant ε>0, the complexity of the vertical decomposition of a set of n triangles in three-dimensional space is O(n^2+ε+K), where K is the complexity of the arrangement of the triangles. For a single cell the complexity of the ...

We consider the problem of bounding the combinatorial complexity of a single cell in an arrangement of n low-degree algebraic surface patches in 3-space. We show that this complexity is O(n^2+ε), for any ε>0, where the constant of proportionality depends ...

Let B be a convex polyhedron translating in 3-space amidst k convex polyhedral obstacles A₁,…,A_k with pairwise disjoint interiors. The free configuration space (space of all collision-free placements) of B can be represented as the complement of the ...

We present an efficient and simple paradigm for motion planning amidst fat obstacles. The paradigm fits in the cell decomposition approach to motion planning and exploits workspace properties that follow from the fatness of the obstacles. These ...

Papadimitriou's approximation approach to the Euclidean shortest path (ESP) problem in 3-space is revisited. As this problem is NP-hard, his approach represents an important step towards practical algorithms. Unfortunately, there are non-trivial gaps in ...

We show that deciding whether a tree can be drawn in the plane so that it is the Euclidean minimum spanning tree of the locations of its vertices is NP-hard.

In this paper, we present an optimal parallel randomized algorithm for the Voronoi diagram of a set of n non-intersecting (except possibly at endpoints) line segments in the plane. Our algorithm runs in O(logn) time with very high probability and uses O(...

We give a simple lazy randomized incremental algorithm to compute ≤k-levels in arrangements of x-monotone Jordan curves in the plane, and in arrangements of planes in three-dimensional space. If each pair of curves intersects in at most s points, the ...

We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. The main new idea is a simple randomized O(nlogn) ...

For two given point sets, we present a very simple (almost trivial) algorithm to translate one set so that the Hausdorff distance between the two sets is not larger than a constant factor times the minimum Hausdorff distance which can be achieved in ...

In this paper we present a new technique for piecewise-linear surface reconstruction from a series of parallel polygonal cross-sections. This is an important problem in medical imaging, surface reconstruction from topographic data, and other ...

We present practical methods for approximate geometric pattern matching in d-dimensions along with experimental data regarding the quality of matches and running times of these methods versus those of a branch-and-bound search. Our methods are faster ...

We devise techniques to manipulate a collection of loosely interpenetrating spheres in three-dimensional space. Our study is motivated by the representation and manipulation of molecular configurations, modeled by a collection of spheres. We analyze the ...

A polyhedron P is castable if its boundary can be partitioned by a plane into two polyhedral terrains. Such polyhedra can be manufactured easily using two cast parts. Assuming that the cast parts are removed by a single translation each, it is shown ...

Let G=(V,E) be a n-vertex connected graph with positive edge weights. A subgraph G′ is a t-spanner if for all u,v ∈ V, the distance between u and v in the subgraph is at most t times the corresponding distance in G. We design an O(nlog²n) time algorithm ...

This paper describes an efficient scheme to dynamically maintain the set of maximas of a 2-d set of points. Using the fact that the maximas can be stored in a Staircase structure, we use a technique which maintains approximations to the Staircase ...

We present a method for maintaining biased search trees so as to support fast finger updates (i.e., updates in which one is given a pointer to the part of the tree being changed). We illustrate the power of such biased finger trees by showing how they ...

This paper gives an algorithm for approximately solving the post office problem: given n points (called sites) in d dimensions, build a data structure so that, given a query point q, a closest site to q can be found quickly. The algorithm is also given ...

Let S be a set of n points in R^D. It is shown that a range tree can be used to find an L_∞ -nearest neighbor in S of any query point, in O((logn)^D-1 loglogn) time. This data structure has size O(n(logn)^D-1) and an amortized update time of O((logn)^D-1 ...

We consider the problem of a robot which has to find a path in an unknown simple polygon from one point s to another point t, based only on what it has seen so far. A Street is a polygon for which the two boundary chains from s to t are mutually weakly ...

A minimum Steiner tree for a given set X of points is a network interconnecting the points of X having minimum possible total length. The Steiner ratio for a metric space is the largest lower bound for the ratio of lengths between a minimum Steiner tree ...

We prove that a (k-1)-separated family of n compact convex sets in R^d can be met byk-transversals in at most O(d)^d2((2^k+1-2 / k) (n / k+1))^k(d-k) or, for fixed k and d, O(n^k(k+1)(d-k)) different order types. This is the first non-trivial bound for 1< k<...

We show that any graph of n vertices that can be drawn in the plane with no k+1 pairwise crossing edges has at most c_knlog^2k−2n edges. This gives a partial answer to a dual version of a well-known problem of Avital-Hanani, Erdős, Kupitz, Perles, and ...

A halving hyperplane of a set S of n points in R^d contains d affinely independent points of S so that equally many of the points off the hyperplane lie in each of the two half-spaces. We prove bounds on the number of halving hyperplanes under the ...

We give an algorithm for triangulating n-vertex polygonal regions (with holes) so that no angle in the final triangulation measures more than π/2. The number of triangles in the triangulation is only O(n), improving a previous bound of O(n²), and the ...

This paper shows that for any plane geometric graph 𝒢 with n vertices, there exists a triangulation 𝒯 conforms to 𝒢, i.e. each edge of 𝒢 is the union of some edges of 𝒯, where 𝒯 has O(n²) vertices with angles of its triangles measuring no more ...

Motivated by practical VLSI routing applications, we study the maximum vertex degree of a minimum spanning tree (MST). We prove that under the L_p norm, the maximum vertex degree over all MSTs is equal to the Hadwiger number of the corresponding unit ...

Given a simple polygon, we present an optimal linear-time algorithm that computes the shortest illuminating line segment, if one exists; else it reports that none exists. This solves an intriguing open problem by improving the O(nlogn)-time algorithm ...