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

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

Sarah Donnelly sarahd at
Wed Sep 25 13:39:35 EDT 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.


Call for Participation:

We expect the workshop to contain both invited and contributed
presentations. Anyone interested in participating in the workshop
should contact one of the organizers.


The following speakers have been confirmed: 

    Herve Bronnimann 
    Ioannis Emiris 
    Steven Fortune 
    Komei Fukuda 
    Martin Held 
    Chris Hoffman 
    John Keyser 
    Sylvain Pion 
    Stefan Schirra 
    Jonathan Shewchuk 
    Ayellet Tal 
    Monique Teillaud 
    Nicola Wolpert 
    Chee Yap 


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