Geometric Computing
Coordinator:
Researchers
Research Area
We have an excellent reputation for publishing efficient and correct
software in algorithms and data structures. Besides their practical
usefulness, these implementation efforts also stimulate new and
exciting research questions for our group, such as efficiency in
practice compared to the O-calculus in theory, understanding of
robustness and degeneracy handling in geometric algorithms, or
correctness checking of complicated algorithms and data structures.
The size of our software projects often implies that we apply
techniques from software engineering and, for example, develop new
solutions following the object-oriented or generic programming
paradigm.
Some of our software modules have reached industrial strength and are
distributed through and further developed together with spin-offs:
LEDA,
LEDA-SM,
BALL together with
Algorithmic Solutions
and
CGAL together with
Geometry Factory. We also
cooperate either directly or
through the spin-offs with a number of industrial partners, e.g.,
Siemens, Daimler-Chrysler, and Lufthansa
Systems.
Software
-
LiS, NiX, SoX, CnX, CbX,
QdX and AlciX: Library Support, NumeriX, SweepX, ConiX,
CubiX, QuadriX and AlciX, part of the
EXACUS project
-
CGAL:
Computational Geometry Algorithms Library
-
LEDA:
Library of Efficient Data types and Algorithms
-
STXXL:
Standard Template Library for Extra Large Data Sets
Sample Publications
-
Arno Eigenwillig, Michael Kerber, Nicola Wolpert: Fast and Exact Geometric Analysis of Real Algebraic Plane Curves. Accepted for the International Symposium on Symbolic and Algebraic Computation (ISSAC 2007)
-
Berberich, E., M. Hemmer, L. Kettner, E. Schömer and N. Wolpert: An exact, complete and efficient implementation for computing planar maps of quadric intersection curves. In: 21st Annual Symp. on Computational Geometry (SCG'05), (Eds.) J. Mitchell, G. Rote, L. Kettner. ACM, New York 2005, 99-106.
-
Berberich, E., A. Eigenwillig, M. Hemmer, S. Hert, L. Kettner, K. Mehlhorn, J. Reichel, S. Schmitt, E. Schömer and N. Wolpert: EXACUS: efficient and exact algorithms for curves and surfaces. In: 13th Annual European Symp. on Algorithms (ESA 2005), Lect. Notes Comput. Sci. 3669, (Eds.) G.S. Brodal, S. Leonardi. Springer, Berlin 2005, 155-166.)
-
A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schönherr:
On the Design of CGAL, the Computational Geometry
Algorithms Library. Software - Practice and Experience 30,
pp. 1167-1202, 2000.
(Abstract)
(PostScript
preprint © John Wiley & Sons Ltd 2000)
-
L. Kettner. Using Generic Programming for Designing a Data Structure
for Polyhedral Surfaces. Computational Geometry -
Theory and Applications 13, pp. 65-90, 1999.
(Abstract)
(PostScript
preprint © Elsevier 1999)
-
K. Mehlhorn, S. Näher: LEDA: A Platform for Combinatorial
and Geometric Computing. Cambridge University Press, 1999.
(Book)
Projects
-
EXACUS: Efficient
and Exact Algorithms for Curves and Surfaces
-
ACS: Algorithms for Complex
Shapes with Certified Topology and Numerics (EU project 2005-2008)
-
ECG: Effective
Computational Geometry for Curves and Surfaces (EU project 2001-2004)
-
ALCOM-FT: Algorithms
and Complexity -- Future Technologies (EU project 2000-2003)
Former Projects and Software
Related Groups
