6301471
Adaptive Simplicial Grids from Cross-Sections of Monotone Complexes
We study the maintenance of a simplicial grid or complex under changing density requirements. The proposed method works in any fixed dimension and generates grids by projecting cross-sections of a monotone simplicial complex that lives in one dimension higher than the grid. The density of the grid is adapted by locally moving the cross-section up or down along the extra dimension.
34884676
Cutting dense point sets in half
A halving hyperplane of a set S of n points in ℝd contains d affinely independent points of S so that equally many of the points off the hyperplane lie in each of the two halfspaces. We prove bounds on the number of halving hyperplanes under the condition that the ratio of largest over smallest distance between any two points is at most δn(1/d), δ some constant. Such a set S is called dense.In d = 2 dimensions the number of halving lines for a dense set can be as much as Ω (n log n), and it cannot exceed O (n5/4/log*n). The upper bound improves over the current best bound of O(n3/2/log*n) which holds more generally without any density assumption. In d = 3 dimensions we show that O(n7/3) is an upper bound on the number of halving planes for a dense set. The proof is based on a metric argument that can be extended to d ≥ 4 dimensions, where it leads to O(nd-2/d) as an upper bound for the number of halving hyperplanes.
12111408
Cutting dense point sets in half
A <italic>halving hyperplane</italic> of a set <italic>S</italic> of <italic>n</italic> points in <bold>R</bold><supscrpt><italic>d</italic></supscrpt> contains <italic>d</italic> affinely independent points of <italic>S</italic> 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 condition that the ratio of largest over smallest distance between any two points is at most δ<italic>n</italic><supscrpt>1/<italic>d</italic></supscrpt>, δ some constant. Such a set <italic>S</italic> is called <italic>dense</italic>.
In <italic>d</italic>=2 dimensions, the number of halving lines for a dense set can be as much as &OHgr;(<italic>n</italic>log<italic>n</italic>), and it cannot exceed <italic>O</italic>(<italic>n</italic><supscrpt>5/4</supscrpt>/log*<italic>n</italic>). The upper bound improves over the current best bound of <italic>O</italic>(<italic>n</italic><supscrpt>3/2</supscrpt>/log*<italic>n</italic>) which holds more generally without any density assumption. In <italic>d</italic>=3 dimensions we show that <italic>O</italic>(<italic>n</italic><supscrpt>7/3</supscrpt>) is an upper bound on the number of halving planes for a dense set. The proof is based on a metric argument that can be extended to <italic>d</italic>≥4 dimensions, where it leads to <italic>O</italic>(<italic>n</italic><supscrpt><italic>d</italic>−2/<italic>d</italic></supscrpt>) as an upper bound for the number of halving hyperplanes.
31366541
An optimal algorithm for constructing the weighted voronoi diagram in the plane
Let S denote a set of n points in the plane such that each point p has assigned a positive weight w(p) which expresses its capability to influence its neighbourhood. In this sense, the weighted distance of an arbitrary point x from p is given by de(x,p)/w(p) where de denotes the Euclidean distance function. The weighted Voronoi diagram for S is a subdivision of the plane such that each point p in S is associated with a region consisting of all points x in the plane for which p is a weighted nearest point of S. 
 
An algorithm which constructs the weighted Voronoi diagram for S in O(n2) time is outlined in this paper. The method is optimal as the diagram can consist of Θ(n2) faces, edges and vertices.
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.
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.
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.
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.