An Empirical Comparison of Software for Constructing Arrangements of Curved Arcs (preliminrary version). Efraim Fogel, Dan Halperin, Ron Wein, Sylvain Pion, Monique Teillaud, Ioannis Emiris, Athanasios Kakargias, Elias Tsigaridas, Eric Berberich, Arno Eigenwillig, Michael Hemmer, Lutz Kettner, Kurt Mehlhorn, Elmar Schömer, and Nicola Wolpert. Technical Report ECG-TR-361200-01, Tel-Aviv University, INRIA Sophia-Antipolis, Max-Planck-Institut für Informatik, 2004.
Arrangements of planar curves are fundamental structures in computational geometry. Algorithms for computing such arrangements consist of a topological part and a geometric part. For both parts different algorithmic approaches and implementations are possible. In ECG, we further developed and implemented these approaches. We followed modern software design and encapsulated our solutions into modules with well-defined and tight interfaces. In particular, we can combine different realizations of the topological part (we have two) with different realizations of the geometric part (we have three, which in turn are parametrized by different implementations of the underlying number types). The implementations of the geometric part follow quite different designs. In this report, we provide first comparisons of our different designs. In a later version of the report, we also plan to compare implementations outside the ECG-project.
The report is preliminary and rises more questions than it answers. We consider it as proof that our modular architecture is valuable and allows us to experiment and compare different approaches. We also consider it as proof for the close cooperation within the project.
[PDF]
[ECG
Project Page]
[CGAL Home Page]
[EXACUS Home Page]