A Tutorial for Designing Flexible Geometric Algorithms
This page contains links to the sorce code and data sets used in the
article A Tutorial for Designing Flexible Geometric Algorithms
[ps.gz,
pdf] by Vikas Kapoor, Dietmar Kühl, and Alexander Wolff
(Algorithmica,
33 (1) 2002,
pp. 52-70).
The implementation of an algorithm is faced with the issues
efficiency, flexibility, and ease-of-use. We suggest a design concept
that greatly increases the flexibility of an implementation without
sacrificing ease-of-use and efficiency.
In order to show the practical relevance and efficiency of our
concept, we compare a generic to a naive implementation of a
rectangle-intersection algorithm in terms of runtime. The following
interface documentations of our implementations are available.
The source code of our
implementations including all example generators and a shell
script that automatically repeats our runtime tests is also available.
The TC-shell, Latex, and gnuplot must be available to produce the
runtime graphs.
We compared our implementations on four sample classes. For each
class (except FencyRect), we generated 30 examples of 1000, 2000, ...,
10000 rectangles. These are available in the zip archives
below.
Here's the old version of this page.
Alexander Wolff
Last modified: Mon Jun 11 04:53:38 MEST 2001