A tutorial for designing flexible geometric algorithms

V. Kapoor, D. Kühl, A. Wolff

    Research output: Contribution to journalArticleAcademicpeer-review

    1 Citation (Scopus)

    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.
    Original languageEnglish
    Pages (from-to)52-70
    JournalAlgorithmica
    Volume33
    Issue number1
    DOIs
    Publication statusPublished - 2002

    Fingerprint Dive into the research topics of 'A tutorial for designing flexible geometric algorithms'. Together they form a unique fingerprint.

    Cite this