30538700
Computing a Ham-Sandwich Cut in Two Dimensions
Let B be a set of n"b black points and W a set of n"w, white points in the Euclidean plane. A line h is said to bisect B (or W) if, at most, half of the points of B (or W) lie on any one side of h. A line that bisects both B and W is called a ham-sandwich cut of B and W. We give an algorithm that computes a ham-sandwich cut of B and W in 0((n"h+n"w) log (min {n"b, n"w}+ 1)) time. The algorithm is considerably simpler than the previous most efficient one which takes 0((n"b + n"w) log (n"b + n"w)) time.
41540520
Space Searching for Intersecting Objects
Determining or counting geometric objects that intersect another geometric query object is at the core of algorithmic problems in a number of applied areas of computer science. This article presents a family of space-efficient data structures that realize sublinear query time for points, line segments, lines and polygons in the plane, and points, line segments, plaraes, and polyhedra in three dimensions.
27184000
On the Intersection of Orthogonal Objects
43503455
Computing the Extreme Distances Between Two Convex Polygons
Abstract A polygon in the plane is convex if it contains all line segments connecting any two of its points. Let P and Q denote two convex polygons. The computational complexity of finding the minimum and maximum distance possible between two points p in P and q in Q is studied. An algorithm is described that determines the minimum distance (together with points p and q that realize it) in O (log m + log n ) time, where m and n denote the number of vertices of P and Q , respectively. This is optimal in the worst case. For computing the maximum distance, a lower bound Ω(m + n) is proved. This bound is also shown to be best possible by establishing an upper bound of O ( m + n ).
22962151
On the Number of Line Separations of a Finite Set in the Plane
Abstract Let S denote a set of n points in the Euclidean plane. A subset S′ of S is termed a k-set of S if it contains k points and there exists a straight line which has no point of S on it and separates S′ from S−S′. We let fk(n) denote the maximum number of k-sets which can be realized by a set of n points. This paper studies the asymptotic behaviour of fk(n) as this function has applications to a number of problems in computational geometry. A lower and an upper bound on fk(n) is established. Both are nontrivial and improve bounds known before. In particular, f k (n) = f n−k (n) = Ω(n log k) is shown by exhibiting special point-sets which realize that many k-sets. In addition, f k (n) = f n−k (n) = O(nk 1 2 ) is proved by the study of a combinatorial problem which is of interest in its own right.
1600979
Three-dimensional alpha shapes
Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is sometimes useful or required to compute what one might call the “shape” of the set. For that purpose, this article introduces the formal notion of the family of α-shapes of a finite point set in R<supscrpt>3</supscrpt>. Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter α ε R controlling the desired level of detail. An algorithm is presented that constructs the entire family of shapes for a given set of size <italic>n</italic> in time <italic>0(n<supscrpt>2</supscrpt>)</italic>, worst case. A robust implementation of the algorithm is discussed, and several applications in the area of scientific computing  are mentioned.
53237055
Three-dimensional alpha shapes
Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is sometimes useful or required to compute what one might call the “shape” of the set. For that purpose, this article introduces the formal notion of the family of α-shapes of a finite point set in R 3 . Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter α e R controlling the desired level of detail. An algorithm is presented that constructs the entire family of shapes for a given set of size n in time 0(n 2 ) , worst case. A robust implementation of the algorithm is discussed, and several applications in the area of scientific computing are mentioned.
46726120
The union of balls and its dual shape
Efficient algorithms are described for computing topological, combinatorial, and metric properties of the union of finitely many spherical balls in ℝd. These algorithms are based on a simplicial complex dual to a decomposition of the union of balls using Voronoi cells, and on short inclusion-exclusion formulas derived from this complex. The algorithms are most relevant in ℝ3 where unions of finitely many balls are commonly used as models of molecules.
9599628
The union of balls and its dual shape
Efficient algorithms are described for computing topological,combinatorial, and metric properties of the union of finitely many ballsin <inline-equation><f><blkbd>R</blkbd><sup>d</sup></f></inline-equation>. These algorithms are based on a simplicial complexdual to a certain decomposition of the union of balls, and on shortinclusion-exclusion formulas derived from this complex. The algorithmsare most relevant in <inline-equation><f><blkbd>R</blkbd><sup>3</sup></f></inline-equation> <?Pub Caret>where unions of finitely many balls arecommonly used as models of molecules.
5215240
Sliver exudation
A sliver is a tetrahedron whose four vertices lie close to a plane and whose projection to that plane is a convex quadrilateral with no short edge. Slivers are notoriously common in 3-dimensional Delaunay triangulations even for well-spaced point sets. We show that if the Delaunay triangulation has the ratio property introduced in [15] then there is an assignment of weights so the weighted Delaunay triangulation contains no slivers. We also give an algorithm to compute such a weight assignment.