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 dimacs.rutgers.edu
Mon Nov 25 17:27:12 EST 2002




DIMACS Workshop on Implementation of Geometric Algorithms

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

Organizers: 
    Herve Bronnimann, Polytechnic University, hbr at poly.edu 
    Steven Fortune, Bell Laboratories, Lucent Technologies, 
          sjf at 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 at 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, IBM Research and Microsoft Research are also
waived.

***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**






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