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 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.
Next: Call for Participation
Workshop Index
DIMACS Homepage