Show icon Show search tips...
Hide icon Hide search tips...

[Sy-cg-global] Program: DIMACS Workshop on Implementation of Geometric Algorithms

Sarah Donnelly sarahd at
Fri Nov 1 16:50:53 EST 2002

DIMACS Workshop on Implementation of Geometric Algorithms

December 4 - 6, 2002
DIMACS Center, Rutgers University, Piscataway NJ 

    Herve Bronnimann, Polytechnic University, hbr at 
    Steven Fortune, Bell Laboratories, Lucent Technologies, 
          sjf at 

Presented under the auspices of the Special Focus on Computational
Geometry and Applications.  


It is notoriously difficult to implement geometric algorithms. This
difficulty arises in part from the conceptual complexity of geometric
algorithms, the proliferation of special cases, the dependence of
combinatorial decisions on numerical computation, and frequent
theoretical focus on worst-case asymptotic behavior.

This workshop will address research issues related to the
implementation of geometric algorithms. Typical, but not exclusive
topics include:

    Numerical issues 
    Noisy data and data repair 
    Geometric data structures 
    Massive geometric data sets 
    Algorithm library design 
    Algorithm engineering 
    Experimental studies 

Numerical issues have long been an important concern in the
implementation of geometric algorithms. In the last decade the issue
has become a central research topic in computational geometry, and a
reasonably successful approach based on the use of exact
(extended-precision) arithmetic has been developed. However, many
significant problems remain---high-level rounding, extension to curved
objects, performance---and the practical impact of the research is not
yet clear.

Geometric data sets based on physical measurements are inherently
noisy. If such geometric data also has combinatorial structure, the
geometric and combinatorial information may be inconsistent. To be
useful, geometric algorithms must be able to repair such data, that
is, in some fashion eliminate inconsistencies. Unfortunately, there is
little relevant theory, and current data repair is heuristic at best.

Geometric data structures are known that can represent complex
structures in any dimension. However massive data sets in two
dimensions, or even modest data sets in high dimension, can require
enormous amounts of memory. A challenging research topic is to design
algorithms and data structures that are cognizant of the memory
hierarchy---cache, main memory, disk---and to provide appropriate

These are just some of the problems faced by general purpose geometric
algorithms libraries. Considerable effort has been expended developing
the geometric algorithm library CGAL, which is now reasonably
mature. CGAL,just together with the LEDA algorithm library, provide an
unparalleled resource for users of geometric algorithms. Further
development of algorithm libraries requires attention to many
issues---those mentioned above, but also functionality, interface,
performance, and support for specific application areas.

We plan to bring together both researchers and practitioners. We hope
that practitioners will benefit from discussions of the state of the
art in research, and that researchers will benefit by being exposed to
implementation issues of practical importance.


WEDNESDAY December 4

 8:15 - 8:55    Breakfast and registration

 8:55 - 9:00    Opening remarks, 
                Fred Roberts, Director of DIMACS

 9:00 - 9:30    Root-comparison techniques and applications 
                  to the Voronoi diagram of Disks
                Ioannis Emiris, University of Athens
 9:30 - 10:00   Progress in constructive root bounds
                Chee Yap, NYU

10:00 - 10:30   Iterative conditioning as an algorithm design 
                  schema for robust geometric predicates
                Steven Fortune, Bell Labs

10:30 - 11:00   break

11:00 - 11:30   Controlled Perturbation for Arrangements of Circles     
                Dan Halperin, Tel Aviv University

11:30 - 12:00   Geometric Conditioning
                Victor Milenkovic, University of Miami

12:00 - 2:00    lunch

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

 2:30 - 3:00    An Exact and Efficient Approach for Computing 
                  a Cell in an Arrangement of Quadrics
                Nicola Wolpert, Max-Planck-Institute for Computer Science
 3:00 - 3:30    Robust Operations on Curved Solids
                John Keyser, Texas A&M University

 3:30 - 4:00    break
 4:00 - 4:30    TBA
                Monique Teillaud, INRIA

 4:30 - 5:00    Efficient Exact Geometric Predicates for Delaunay 
                Sylvain Pion, MPI Saarbruecken

Thursday  December 5

 8:30 - 9:00    Breakfast 

 9:00 - 9:30    Data Structures and Design of a 3D Mesh Generator
                Jonathan Shewchuk, Berkeley

 9:30 - 10:00   Boolean Operations on 3D Surfaces Using Nef Polyhedra
                Lutz Kettner, MPI Informatik, Germany
10:00 - 10:30   TBA
                Stefan Schirra

10:30 - 11:00   break

11:00 - 11:30   Experiences With Designing and Implementing "Industrial-
                  Strength" Codes for Handling "Industrial-Quality" 
                  Data in Real-World Applications
                Martin Held, Salzburg

11:30 - 12:00   TBA
                Andreas Fabri

12:00 - 2:00    lunch

 2:00 - 2:30    JDSL: the Data Structures Library in Java
                Roberto Tamassia, Brown

 2:30 - 3:00    TBA
                Herve Bronnimann, Polytechnic
 3:00 - 3:30    Algorithm library development for complex biological 
                  and mechanical systems: functionality, 
                  interoperability and numerical stability
                Marina Gavrilova, University of Calgary

 3:30 - 4:00    break
 4:00 - 6:00    Panel Discussion: What next for computational 
                  geometry software?
                Nina Amenta, Andreas Fabri, Steven Fortune, 
                  Jonathan Shewchuk     

 6:00 - 7:30    Dinner (DIMACS Lounge, Room 401, CoRE Bldg.)

Friday December 6

 8:30 - 9:00    Breakfast 

 9:00 - 9:30    TBA
                Shankar Krishnan, ATT
 9:30 - 10:00   Blocked Randomized Incremental Constructions
                Nina Amenta, Sunghee Choi,  University of Texas, Austin

10:00 - 10:30   A Parallel Implementation of an Arrangement 
                  Construction Algorithm
                Komei Fukuda, McGill

10:30 - 11:00   break

11:00 - 11:30   Fast Penetration Depth Estimation: Algorithms, 
                  Implementation & Applications
                Ming Lin, UNC Chapel Hill

11:30 - 12:00   Voronoi diagrams for VLSI manufacturing: Robustness
                  and implementation issues
                Evanthia Papadopoulou, IBM T.J. Watson Research Center

12:00 - 1:30    lunch

 1:30 - 2:00    TBA
                David Warme, L-3Com

 2:00 - 2:30    Polyhedral Surface Decomposition and Applications
                Ayellet Tal, Princeton/Technion


Registration Fees:

Registration: (Pre-registration date: November 27, 2002)

Regular rate
Preregister before deadline $120/day
After preregistration deadline $140/day

Reduced Rate*
Preregister before deadline $60/day
After preregistration deadline $70/day

Preregister before deadline $10/day
After preregistration deadline $15/day

DIMACS Postdocs $0

Non-Local Graduate & Undergraduate students
Preregister before deadline $5/day
After preregistration deadline $10/day

Local Graduate & Undergraduate students $0
(Rutgers & Princeton)

DIMACS partner institution employees** $0

DIMACS long-term visitors*** $0

Registration fee to be collected on site, cash, check, VISA/Mastercard

Our funding agencies require that we charge a registration fee for the
workshop. Registration fees cover participation in the workshop, all
workshop materials, breakfast, lunch, breaks, and any scheduled social
events (if applicable).

* College/University faculty and employees of non-profit organizations
will automatically receive the reduced rate. Other participants may
apply for a reduction of fees. They should email their request for the
reduced fee to the Workshop Coordinator at
workshop at Include your name, the Institution you
work for, your job title and a brief explanation of your
situation. All requests for reduced rates must be received before the
preregistration deadline. You will promptly be notified as to the
decision about it.

** Fees for employees of DIMACS partner institutions are waived.
DIMACS partner institutions are: Rutgers University, Princeton
University, AT&T Labs - Research, Bell Labs, NEC Research Institute
and Telcordia Technologies. Fees for employees of DIMACS affiliate
members Avaya Labs and Microsoft Research are also waived. Fees are
not waived for IBM Watson Research Center employees (the terms of the
IBM membership are different from the Avaya and Microsoft agreements).

***DIMACS long-term visitors who are in residence at DIMACS for two or
more weeks inclusive of dates of workshop.


Information on participation, registration, accommodations, and travel
can be found at:


More information about the Dimacs-sy-cg-global mailing list