14707519
Inequalities for the curvature of curves and surfaces
In this paper, we bound the difference between the total mean curvatures of two closed surfaces in R3 in terms of their total absolute curvatures and the Fréchet distance between the volumes they enclose. The proof relies on a combination of methods from algebraic topology and integral geometry. We also bound the difference between the lengths of two curves using the same methods.
17520762
Extraction and simplification of iso-surfaces in tandem
The tandem algorithm combines the marching cube algorithm for surface extraction and the edge contraction algorithm for surface simplification in lock-step to avoid the costly intermediate step of storing the entire extracted surface triangulation. Beyond this basic strategy, we introduce refinements to prevent artifacts in the resulting triangulation, first, by carefully monitoring the amount of simplification during the process and, second, by driving the simplification toward a compromise between shape approximation and mesh quality. We have implemented the algorithm and used extensive computational experiments to document the effects of various design options and to further fine-tune the algorithm.
43503455
Computing the Extreme Distances Between Two Convex Polygons
Abstract A polygon in the plane is convex if it contains all line segments connecting any two of its points. Let P and Q denote two convex polygons. The computational complexity of finding the minimum and maximum distance possible between two points p in P and q in Q is studied. An algorithm is described that determines the minimum distance (together with points p and q that realize it) in O (log m + log n ) time, where m and n denote the number of vertices of P and Q , respectively. This is optimal in the worst case. For computing the maximum distance, a lower bound Ω(m + n) is proved. This bound is also shown to be best possible by establishing an upper bound of O ( m + n ).
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.
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.


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.
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.