DIMACS Workshop on Implementation of Geometric Algorithms

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

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

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
implementations.

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.


**************************************************************

Workshop Program:

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	Progress on the number type leda::real
		Stefan Schirra

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   Controlled Perturbation for Arrangements of Circles
		Dan Halperin, Tel Aviv University

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

12:30 - 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   	Towards a CGAL Geometric Kernel with Circular Arcs
		Monique Teillaud, INRIA

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

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


Thursday  December 5

 8:30 - 9:00	Breakfast and registration

 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	Algorithms in polytope theory and polymake
                Michael Joswig, Technische Universität

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	From a Library to Geometric Software Components
		Andreas Fabri, Geometry Factory

12:00 - 2:00	Lunch

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

 2:30 - 3:00	Towards Generic Software Components?
		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 and registration

 9:00 - 9:30	Implementing Geometric Algorithms using
                  Graphics Hardware
		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   TBA 
                Kenneth L. Clarkson, Bell Labs

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	Geometric and Numeric Stability Issues in GeoSteiner
		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

Postdocs
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
accepted.

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@dimacs.rutgers.edu. 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:


       http://dimacs.rutgers.edu/Workshops/GeomAlgorithms/


           **PLEASE BE SURE TO PRE-REGISTER EARLY**

_______________________________________________
Publicity-list mailing list
Publicity-list@dimax.rutgers.edu
http://dimax.rutgers.edu/mailman/listinfo/publicity-list