DIMACS Center, Rutgers University, Piscataway NJ

**Organizers:****Herve Bronnimann**, Polytechnic University, hbr@poly.edu**Steven Fortune**, Bell Laboratories, Lucent Technologies, sjf@bell-labs.com

Nina Amenta, University of Texas at AustinTitle: Blocked Randomized Incremental Constructions

Herve Bronnimann, Polytechnic UniversityTitle: Towards Generic Software Components?

Sunghee Choi, University of Texas at AustinTitle: Blocked Randomized Incremental Constructions

Ken Clarkson, Bell LabsTitle: A Code for Nearest Neighbor Searching in Metric Spaces

Given a set of sites, the nearest neighbor searching problem is to build a data structure so that the site nearest a query point can be found quickly. I'll describe an kd-tree-like approach to this problem in the setting of metric spaces, and discuss an implementation, some experiments, and a test harness. The goal here is a library routine that is "pretty ok": uses moderate storage, fast in low dimension, never worse than brute force.

Ioannis Emiris, University of Athens, GreeceTitle: Root-comparison techniques and applications to the Voronoi diagram of disks

This talk reviews algebraic approaches for comparing quadratic algebraic numbers, thus yielding methods for deciding key predicates in various geometric constructions. In particular, our main motivation and application is the dynamic algorithm by Karavelas and Yvinec for computing the Voronoi diagram of disks in the plane, also known as additively-weighted Voronoi diagram or the Apollonius diagram.

We focus on methods based on polynomial Sturm sequences, which yield an efficient, exact, and complete algorithm; completeness here refers to the handling of all degenerate cases. Our approach minimizes the algebraic degree of the computed quantities as well as the total number of arithmetic operations. This answers the twofold goal of minimizing precision as well as bit complexity. Interestingly, the bottleneck of our algorithm concerns the same operations as with other approaches. Ancillary tools include geometric invariants, multivariate factorization, and multivariate resultants. An implementation of these methods demonstrates their practical performance.

This work, to be presented at SODA 2003, is joint with Menelaos Karavelas.

Andreas Fabri, Geometry FactoryTitle: From a Library to Geometric Software Components

Title: Iteartive conditioning as an algorithm design schema for robust geometric predicates

W. Randolph Franklin, Rensselaer Polytechnic InstituteTitle: Geometric Operations on Hundreds of Millions of Objects

Komei Fukuda, School of Computer Science, McGill UniversityTitle: A Parallel Implementation of an Arrangement Construction Algorithm

Marina Gavrilova, University of Calgary

Dan Halperin, Tel Aviv UniversityTitle: Controlled Perturbation for Arrangements of Circles

Joint work with Eran Leiserowitz

Martin Held, University of Salzberg

Michael Hemmer, Max-Planck-Institut fur InformatikTitle: A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons

Title: Algorithms in polytope theory and polymake

Lutz Kettner, MPI Informatik, GermanyTitle: Boolean Operations on 3D Surfaces Using Nef Polyhedra

John Keyser, Texas A&M UniversityTitle: Robust Operations on Curved Solids

Shankar Krishnan, AT&T Labs - ResearchTitle: Implementing Geometric Algorithms using Graphics Hardware

Ming Lin, University of North Carolina at Chapel HillTitle: Fast Penetration Depth Estimation: Algorithms, Implementation & Applications

Victor Milenkovic, University of Miami

Evanthia Papadopoulou, IBM T.J. Watson Research CenterTitle: Voronoi diagrams for VLSI manufacturing: Robustness and implementation issues

Sylvain Poin, MPI SaarbrueckenTitle: Efficient Exact Geometric Predicates for Delaunay Triangulations

In this paper, we propose, in the context of three dimensional Delaunay triangulations:

- semi-automatic tools for the writing of static and semi-static filters,
- a new semi-static level of filtering called translation filter,
- detailed benchmarks of the success rates of these filters and comparison with rounded arithmetic, long integer arithmetic and filters provided in Shewchuk's predicates.

Our method is general and can be applied to all geometric predicates on points that can be expressed as signs of polynomial expressions. This work is applied in the CGAL library.

This is joint work with Olivier Devillers.

**Stefan Schirra**, University of Magdeburg

Title: Progress on the number type leda::real

Title: Pyramid: Data Structures and Design of a 3D Mesh Generator

I discuss the algorithmic design, data structures, and robustness issues of implementing Pyramid, a three-dimensional constrained Delaunay tetrahedralizer and mesh generator.

Title: Polyhedral Surface Decomposition and Applications

The problem of decomposing a polyhedron into (convex) pieces has been exhaustively researched in computational geometry. Despite the large number of potential applications, little of this research has been used in practice. There are a couple of possible explanations. First, programming these algorithms can be challenging and might involve solutions to various numerical problems. Second, the size of the decomposition might be quadratic, which is often prohibitive in real applications.

In various applications, however, it suffices to decompose only the polyhedral surface. In this case not only the implementation becomes simpler, but also the size of the decomposition is linear. Numerical problems, however, often cause over-segmentation.

We will present a novel algorithm which avoids over segmentation. The algorithm decomposes any given surface into a handful of patches regardless of the description size of the surface. In fact, the user can determine in advance the desirable size of the decomposition. This is an important feature since certain applications require only a few patches.

Our algorithm has an added benefit. Rather than focusing solely on the shape of the patches, as is customary, the shape of the cuts is also taken into account.

The research presented here is of an experimental nature, and we will thus discuss various possible applications. Moreover, we will demonstrate some results obtained for two specific applications: metamorphosis of polyhedral surfaces and shape-based retrieval of polyhedral surfaces.

**Roberto Tamassia**, Brown University

Title: JDSL: the Data Structures Library in Java

Title: Towards a CGAL Geometric Kernel with Circular Arcs

**David Warme**, L-3 Communication Analytics Corp.

Title: Geometric and Numeric Stability Issues in GeoSteiner

**Nicola Wolpert**, Max-Planck-Institute for Computer Science

Title: An Exact and Efficient Approach for Computing a Cell in an Arrangement of Quadrics

Title: Progress in Constructive Root Bounds

Next: Call for Participation

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on October 2, 2002.