30416185
On the Zone Theorem for Hyperplane Arrangements
The zone theorem for an arrangement of n hyperplanes in d-dimensional real space says that the total number of faces bounding the cells intersected by another hyperplane is $O(n^{d - 1} )$. This result is the basis of a time-optimal incremental algorithm that constructs a hyperplane arrangement and has a host of other algorithmic and combinatorial applications. Unfortunately, the original proof of the zone theorem, for $d \geqslant 3$, turned out to contain a serious and irreparable error. This paper presents a new proof of the theorem. The proof is based on an inductive argument, which also applies in the case of pseudohyperplane arrangements. The fallacies of the old proof along with some ways of partially saving that approach are briefly discussed.
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.
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.
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.
16373684
Counting triangle crossings and halving planes
Every collection of t ≥ 2n<supscrpt>2</supscrpt> triangles witha total of n vertices in <inline-equation><f><blkbd>R</blkbd><sup>3</sup></f></inline-equation> has <inline-equation><f><g>W</g><fen lp="par"><fr><nu>t<sup>4</sup></nu><de>n<sup>6</sup></de></fr><rp post="par"></fen></f></inline-equation> crossing pairs. This implies that one of their edgesmeets<inline-equation><f><g>W</g><fen lp="par"><fr><nu>t<sup>3</sup></nu><de>n<sup>6</sup></de></fr><rp post="par"></fen></f><?Pub Caret></inline-equation> of the triangles. From this it followsthat n points in <inline-equation><f><blkbd>R</blkbd><sup>3</sup></f></inline-equation> have only O(n<supscrpt>8/3</supscrpt>) halvingplanes.
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.
17780302
Triangulating topological spaces
Given a subspace<inline-equation><f><blkbd>X⊆R</blkbd><sup>d</sup></f></inline-equation> and a finite set <inline-equation><f>S⊆<blkbd>R</blkbd><sup>d</sup></f></inline-equation>, we introduce the Delaunay simplicial complex, <inline-equation><f><sc>D</sc><inf><blkbd>X</blkbd></inf></f></inline-equation>, restricted by <inline-equation><f><blkbd>X</blkbd></f></inline-equation>. Its simplices are spanned by subsets<inline-equation><f>T⊆S</f></inline-equation> for which the common intersection of Voronoi cells meets <inline-equation><f><blkbd>X</blkbd></f></inline-equation> in a non-empty set. By the nerve theorem,<inline-equation><f><lim align="c"><op>⋃</op></lim><sc>D</sc><inf><blkbd>X</blkbd></inf></f></inline-equation> and <inline-equation><f><blkbd>X</blkbd></f></inline-equation> are homotopy equivalent if all such sets are contractible. This paper shows that <inline-equation><f><lim align="c"><op>⋃</op></lim><sc>D</sc><inf><blkbd>X</blkbd></inf></f></inline-equation> and <inline-equation><f><blkbd>X</blkbd></f></inline-equation> <?Pub Caret1>are homeomorphic if the sets can be further subdivided in a certain way so they form a regular CW complex.
7437367
Vines and vineyards by updating persistence in linear time
Persistent homology is the mathematical core of recent work on shape, including reconstruction, recognition, and matching. Its pertinent information is encapsulated by a pairing of the critical values of a function, visualized by points forming a diagram in the plane. The original algorithm in [10] computes the pairs from an ordering of the simplices in a triangulation and takes worst-case time cubic in the number of simplices. The main result of this paper is an algorithm that maintains the pairing in worst-case linear time per transposition in the ordering. A side-effect of the algorithm's analysis is an elementary proof of the stability of persistence diagrams [7] in the special case of piecewise-linear functions. We use the algorithm to compute 1-parameter families of diagrams which we apply to the study of protein folding trajectories.
10864618
Stability of persistence diagrams
The persistence diagram of a real-valued function on a topological space is a multiset of points in the extended plane. We prove that under mild assumptions on the function, the persistence diagram is stable: small changes in the function imply only small changes in the diagram. We apply this result to estimating the homology of sets in a metric space and to comparing and classifying geometric shapes.
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.