A Generic Design Concept for Geometric Algorithms

Vikas Kapoor
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin
email: kapoor@inf.fu-berlin.de

Dietmar Kühl
Claas Solutions GmbH
email: dietmar.kuehl@claas-solutions.de

Alexander Wolff
Ernst-Moritz-Arndt Universtität Greifswald
Institut für Mathematik und Informatik
email: awolff@mail.uni-greifswald.de

Report B 00-10
June 2000

Abstract The design phase of an algorithm's implementation is confronted with the issues of efficiency, flexibility, and ease-of-use. In this paper, we suggest a concept that greatly increases the flexibility of an implementation without sacrificing its ease-of-use. The loss in terms of efficiency is small.

We demonstrate the advantages of our concept at a CC ++ implementation of a simple rectangle-intersection algorithm, which follows the well-known sweep-line paradigm. We lead the reader from a naive interface in a step-by-step guide to an interface offering full flexibility. The gain in flexibility can reduce implementation effort by facilitating code reusage. Reusability in turn helps to achieve correctness since more users mean more testing.

Though most of the ingredients of our concept have already been suggested elsewhere, to our knowledge this is the first time that they are applied vigorously in a geometric setting.

We include a thorough experimental analysis on random and real world data that arouse in the context of map labeling.

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-00-10.ps.gz