12582971
Stabbing line segments
An algorithm for the geometric problem of determining a line (called a stabbing line) which intersects each ofn given line segments in the plane is presented. As a matter of fact, the algorithm computes a description of all stabbing lines. A purely geometric fact is proved which infers that this description requiresO(n) space to be specified. Our algorithm computes it inO(n logn) time which is optimal in the worst case.Using the description of the stabbing lines, we are able to decide inO(logn) time whether or not a specified line is a stabbing line. Finally, the problem of maintaining the description of all stabbing lines while inserting and deleting line segments is addressed.
2265636
Polygonal Intersection Searching
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.
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.
46103497
Loops in Reeb Graphs of 
2-Manifolds
Abstract
 Given a Morse function f over a 2-manifold with or without boundary,
 the Reeb graph is obtained by contracting the connected components
 of the level sets to points.
 We prove tight upper and lower bounds on the
 number of loops in the Reeb graph
 that depend on the genus, the number of boundary components,
 and whether or not the 2-manifold is orientable.
 We also give an algorithm that constructs the Reeb graph in time
 O(n log n), where n is the number of edges in the
 triangulation used to represent the 2-manifold and the Morse function.


9524011
On the Definition and the Construction of Pockets in Macromolecules
The shape of a protein is important for its functions. This includes the location and size of identifiable regions in its complement space. We formally define pockets as regions in the complement with limited accessibility from the outside. Pockets can be efficiently constructed by an algorithm based on alpha complexes. The algorithm is implemented and applied to proteins with known three-dimensional conformations.
13608907
180 Wrapped Tubes
The 180 models collected in this paper are produced by sampling and wrapping point sets on tubes. The surfaces are represented as triangulated 2-manifolds and available as stl- files from the author's web site atwww.cs.duke.edu/ edels. Each tube is obtained by thickening a circle or a smooth torus knot, and for some we use the degrees of freedom in the thickening process to encode meaningful information, such as curvature or torsion.
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.