27184000
On the Intersection of Orthogonal Objects
33731652
Rectangular Point Location in d Dimensions with Applications
2265636
Polygonal Intersection Searching
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.
17674541
Some methods of computational geometry applied to computer graphics
Abstract Windowing a two-dimensional picture means to determine those line segments of the picture that are visible through an axis-parallel window. A study of some algorithmic problems involved in windowing a picture is offered. Some methods from computational geometry are exploited to store the picture in a computer such that (1) those line segments inside or partially inside of a window can be determined efficiently, and (2) the set of those line segments can be maintained efficiently while the window is moved parallel to a coordinate axis and/or it is enlarged or reduced.
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.
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.
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.
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.
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.
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.