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.


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.
3265202
Emerging Challenges in Computational Topology
Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both computation and topology.
444430
Loops in reeb graphs of 2-manifolds
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(nlogn), where n is the number of edges in the triangulation used to represent the 2-manifold and the Morse function.
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.
44420378
Triangulating Topological Spaces
Given a subspace ${\Bbb X} \subseteq {\Bbb R}^d$ and a finite set S⊆ℝd, we introduce the Delaunay complex, ${\cal D}_{\Bbb X}$, restricted by ${\Bbb X}$. Its simplices are spanned by subsets T⊆S for which the common intersection of Voronoi cells meets ${\Bbb X}$ in a non-empty set. By the nerve theorem, $\bigcup {\cal D}_{\Bbb X}$ and ${\Bbb X}$ are homotopy equivalent if all such sets are contractible. This paper proves a sufficient condition for $\bigcup {\cal D}_{\Bbb X}$ and ${\Bbb X}$ be homeomorphic.
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.
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.
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.
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.
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.