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.
%0 Journal Article
%1 kkw-tdfga-02
%A Kapoor, Vikas
%A Kühl, Dietmar
%A Wolff, Alexander
%D 2002
%J Algorithmica
%K C++ Standard_Template_Library generic_design myown sweep-line_algorithm
%N 1
%P 52--70
%R 10.1007/s00453-001-0104-9
%T A Tutorial for Designing Flexible Geometric
Algorithms
%V 33
%X 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.
@article{kkw-tdfga-02,
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. \par 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. \par 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.},
added-at = {2024-07-14T10:03:47.000+0200},
author = {Kapoor, Vikas and Kühl, Dietmar and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/2f2e29a1cb89dcbe9f81267ef24022a60/awolff},
cites = {cms-esapf-95, em-ioo-81, fgkss-dcgal-00, k-ugpdd-99,
kkw-gdcga-00, k-dpiga-96, kw-dat-97, nm-lledt-89,
mn-lpcgc-99, ms-stltr-96, nw-clcig-96, o-dcgal-96,
sll-ggcl-99, sll-ggcl-00, w-rasco-97, w-uticd-98,
ZZZ},
doi = {10.1007/s00453-001-0104-9},
interhash = {d3dbd1f9b02015592c7c3c87d700f456},
intrahash = {f2e29a1cb89dcbe9f81267ef24022a60},
journal = {Algorithmica},
keywords = {C++ Standard_Template_Library generic_design myown sweep-line_algorithm},
number = 1,
pages = {52--70},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/kkw-tdfga-02.pdf},
succeeds = {kkw-gdcga-00},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {A Tutorial for Designing Flexible Geometric
Algorithms},
volume = 33,
year = 2002
}