A Tutorial for Designing Flexible Geometric
Algorithms
Algorithmica, 33 (1):
52--70 (2002)DOI: 10.1007/s00453-001-0104-9
Abstract
The implementation of an algorithm is faced with the
issues of efficiency, flexibility, and
ease-of-use. In this paper we suggest a design
concept that greatly increases the flexibility of an
implementation without sacrificing ease-of-use and
efficiency. We demonstrate the advantages of
our concept through a C++ implementation of a simple
rectangle-intersection algorithm, which follows the
well-known sweep-line paradigm. We lead the reader,
who should be familiar with C++ and its template
mechanism, from a naive interface in a step-by-step
guide to an interface offering full flexibility. The
gain in flexibility can reduce the overall
implementation effort by facilitating code
reuse. Reusability in turn helps to achieve
correctness simply because 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.
