2002 Proceeding- Conference Chairs:
- Ferran Hurtado,
- Vera Sacristán,
- Program Chairs:
- Chandrajit Bajaj,
- Subhash Suri
The papers in this volume were presented at the 18th Annual ACM Symposium on Computational Geometry, held June 5-7, 2002, in Barcelona, Spain. The conference included research papers of both an applied and theoretical nature, as well as a video review of geometric algorithms. In addition, there were three invited talks on a topics related to theoretical and applied computational geometry.The symposium was sponsored by SIGGRAPH and SIGACT, two of the Special Interest Groups of the Association for Computing Machinery, and Universitat Politècnica de Catalunya, Spain.In the past, the papers of the applied and theoretical tracks were reviewed by separate program committees, and the presentation of the talks were also essentially kept to separate sessions. In 2002, however, the symposium switched to an integrated format, in which a single program committee reviewed all submissions. Papers were not tagged as applied or theoretical, but rather judged on their research contribution to the field of computational geometry. There were altogether 104 submissions in response to the call for papers, from which the program committee selected 35.The papers appearing in these proceedings generally represent preliminary results of ongoing research. It is expected that most papers will eventually appear in a more polished and complete form in refereed journals.
Parametric search made practical
In this paper we show that in sorting-based applications of parametric search, Quicksort can replace the parallel sorting algorithms that are usually advocated, and we argue that Cole's optimization of certain parametric-search algorithms may be ...
A local search approximation algorithm for k-means clustering
In k-means clustering we are given a set of n data points in d-dimensional space ℜd and an integer k, and the problem is to determine a set of k points in ℜd, called centers, to minimize the mean squared distance from each data point to its nearest ...
On the crossing number of complete graphs
(MATH) Let $\overlinecr(G)$ denote the rectilinear crossing number of a graph $G. We determine $\overlinecr(K 11)=102 and $\overlinecr(K 12)=153. Despite the remarkable hunt for crossing numbers of the complete graph .K n -- initiated by R. Guy in the ...
On the number of embeddings of minimally rigid graphs
(MATH) Rigid frameworks in some Euclidian space are embedded graphs having a unique local realization (up to Euclidian motions) for the given edge lengths, although globally they may have several. We study first the number of distinct planar embeddings ...
Collision detection for deforming necklaces
In this paper, we propose to study deformable necklaces --- flexible chains of balls, called beads, in which only adjacent balls may intersect. Such objects can be used to model macro-molecules, muscles, rope, and other 'linear' objects in the physical ...
Efficient maintenance and self-collision testing for Kinematic Chains
The kinematic chain is a ubiquitous and extensively studied representation in robotics as well as a useful model for studying the motion of biological macro-molecules. Both fields stand to benefit from algorithms for efficient maintenance and collision ...
Box-trees for collision checking in industrial installations
A box-tree is a bounding-volume hierarchy that uses axis-aligned boxes as bounding volumes. We describe a new algorithm to construct a box-tree for a 3D scene consisting of n objects, and we analyze its worst-case query time for approximate range ...
Finite metric spaces: combinatorics, geometry and algorithms
In the last several years a number of very interesting results were proved about finite metric spaces. Some of this work is motivated by practical considerations: Large data sets (coming e.g. from computational molecular biology, brain research or data ...
Finding the consensus shape for a protein family
We define and prove properties of the consensus shape for a family of proteins, a protein-like structure that provides a compact summary of the significant structural information for a protein family. If all members of a protein family exhibit a ...
Paper position sensing
We describe position sensing algorithms used in an airjet paper moving system built at Xerox PARC. The algorithms combine inputs from optical sensors and compute the rectangle best fitting the data. We consider two different types of sensors: fax scan ...
A global approach to automatic solution of jigsaw puzzles
We present a new algorithm for automatically solving jigsaw puzzles by shape alone. The algorithm can solve more difficult puzzles than could be solved before, without the use of backtracking or branch-and-bound. The algorithm can handle puzzles in ...
The power of nonmonotonicity in geometric searching
(MATH) We define a close variant of line range searching over the reals and prove that its arithmetic complexity is $\Theta(n log n) if field operations are allowed and $\Theta(n 3/2) if only additions are. This provides the first nontrivial separation ...
A lower bound on the distortion of embedding planar metrics into Euclidean space
(MATH) We exhibit a simple infinite family of series-parallel graphs that cannot be metrically embedded into Euclidean space with distortion smaller than $\Omega(\sqrt\log n\,)$. This matches Rao's general upper bound for metric embedding of planar ...
The one-round Voronoi game
(MATH) In the one-round Voronoi game, the first player chooses an n-point set $\PFRST$ in a square $Q$, and then the second player places another n-point set $\PSCND$ into $Q$. The payoff for the second player is the fraction of the area of $Q$ occupied ...
Point-line incidences in space
(MATH) Given a set L of n lines in $\reals^3$, let JL denote the set of all joints of L; joints are points in $\reals^3$ that are incident to at least three non-coplanar lines in L. We show that there are at most O(n 5/3) incidences between JL and L.(...
Incidences between points and circles in three and higher dimensions
(MATH) We show that the number of incidences between m distinct points and n distinct circles in $\reals^3$ is O(m 4/7 n 17/21+m 2/3 n 2/3+m+n); the bound is optimal for m n 3/2. This result extends recent work on point-circle incidences in the plane, ...
Lenses in arrangements of pseudo-circles and their applications
(MATH) A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an empty lens if it ...
Pseudotriangulations, polytopes, and how to expand linkages
I will survey some recent results about unfolding of linkages and connections to pseudotriangulations.
Guaranteed: quality parallel delaunay refinement for restricted polyhedral domains
We describe a distributed memory parallel Delaunay refinement algorithm for polyhedral domains which can generate meshes containing tetrahedra with circumradius to shortest edge ratio less than 2, as long as the angle separating any two incident ...
The Delaunay tetrahedralization from Delaunay triangulated surfaces
Given a surface mesh F in R 3 with vertex set S and consisting of Delaunay triangles, we want to construct the Delaunay tetrahedralization of S.We present an algorithm which constructs the Delaunay tetrahedralization of S given a bounded degree spanning ...
Quickest paths, straight skeletons, and the city Voronoi diagram
The city Voronoi diagram is induced by quickest paths, in the L 1 plane speeded up by an isothetic transportation network. We investigate the rich geometric and algorithmic properties of city Voronoi diagrams, and report on their use in processing ...
Testing Homotopy for paths in the plane
In this paper we present an efficient algorithm to test if two given paths are homotopic; that is, whether they wind around obstacles in the plane in the same way. For simple paths specified by n line segments with obstacles described by n points, our ...
Pseudo approximation algorithms, with applications to optimal motion planning
(MATH) We introduce a technique for computing approximate solutions to optimization problems. If X is the set of feasible solutions, the standard goal of approximation algorithms is to compute χ ε X that is an ε-approximate solution in the following ...
Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons
We describe how to construct and kinetically maintain a tessellation of the free space between a collection of k disjoint simple polygonal objects with a total of N vertices, R of which are reflex. Our linear size tessellation consists of pseudo-...
Interlocked open linkages with few joints
We advance the study of collections of open linkages in 3-space that may be interlocked in the sense that the linkages cannot be separated without one bar crossing through another. We consider chains of bars connected with rigid joints, revolute joints, ...
Conforming Delaunay triangulations in 3D
We describe an algorithm which, for any piecewise linear complex (PLC) in 3D, builds a Delaunay triangulation conforming to this PLC.The algorithm has been implemented, and yields in practice a relatively small number of Steiner points due to the fact ...
The probabilistic complexity of the Voronoi diagram of points on a polyhedron
(MATH) It is well known that the complexity, i.e., the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Θ(n 2). Interest has recently arisen as to what happens, both in deterministic and ...
Three dimensional euclidean Voronoi diagrams of lines with a fixed number of orientations
(MATH) We show that the combinatorial complexity of the Euclidean Voronoi diagram of n lines in $\reals3 that have at most c distinct orientations, is O(c 4 n 2+ε), for any ε>0. This result is a step towards proving the long-standing conjecture that the ...
Polyhedral Voronoi diagrams of polyhedra in three dimensions
We show that that the complexity of the Voronoi diagram of a collection of disjoint polyhedra in 3-space that have n vertices overall, under a convex distance function induced by a polyhedron with O(1) facets, is O(n 2+ε), for any ε>0. We also show that ...
