33731652
Rectangular Point Location in d Dimensions with Applications
7249846
Space Searching for Intersecting Objects
Abstract 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, planes, and polyhedra in three dimensions.
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.
2265636
Polygonal Intersection Searching
1993090
Morse-smale complexes for piecewise linear 3-manifolds
We define the Morse-Smale complex of a Morse function over a 3-manifold as the overlay of the descending and ascending manifolds of all critical points. In the generic case, its 3-dimensional cells are shaped like crystals and are separated by quadrangular faces. In this paper, we give a combinatorial algorithm for constructing such complexes for piecewise linear data.
6983029
On the shape of a set of points in the plane
A generalization of the convex hull of a finite set of points in the plane is introduced and analyzed. This generalization leads to a family of straight-line graphs, " \alpha -shapes," which seem to capture the intuitive notions of "fine shape" and "crude shape" of point sets. It is shown that a-shapes are subgraphs of the closest point or furthest point Delaunay triangulation. Relying on this result an optimal O(n \log n) algorithm that constructs \alpha -shapes is developed.
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.
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.
8396933
Hierarchical morse complexes for piecewise linear 2-manifolds
We present algorithms for constructing a hierarchy of increasingly coa rse Morse complexes that decompose a piecewise linear 2-manifold. While Morse complexes are defined only in the smooth category, we extend the construction to the piecewise linear category by ensuring structural integrity and simulating differentiability. We then simplify Morse complexes by cancelling pairs of critical points in order of increasing persistence.