Acknowledgments
Peter Schorn is the main architect of the XYZ GeoBench; Christoph Ammann,
Michele De Lorenzi, Adrian Briingger and many students have made valuable
contributions. Thanks to Nora Sleumer for helping with the production of this
chapter.
References
[dBvKOS97]
[For86]
[tINS88]
[HNS92]
[Kle97]
[Meh84]
[Mut94]
[NH931
[Nie94]
[NSdL+91]
[PS85]
[Sch921
[SH75]
[Vai89]
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Com-
putational Geometry. Springer, 1997.
S. Fortune. A sweepline algorithm for Voronoi diagrams. In Proc. 2nd
Annu. ACM Sympos. Comput. Geom., pages 313-322, 1986.
K. Hinrichs, J. Nievergelt, and P. Schorn. Plane-sweep solves the closest
pair problem elegantly. Inform. Process. Lett., 26:255-261, 1988.
K. Hinrichs, J. Nievergelt, and P. Schorn. An all-round sweep algorithm
for 2-dimensional nearest-neighbor problems. In Acta Informatica, vol-
ume 29, pages 383-394, 1992.
R. Klein. Algorithmische Geometrie. Addision-Wesley, 1997.
K. Mehlhorn. Data Structures and Algorithms 3: Multi-dimensional
Searching and Computational Geometry, volume 3 of EATCS Monographs
on Theoretical Computer Science. Springer-Verlag, Heidelberg, West Ger-
many, 1984.
K. Mulmuley. Computational Geometry: An Introduction Through Ran-
domized Algorithms. Prentice Halt, Englewood Cliffs, N J, 1994.
J. Nievergelt and K. Hinrichs. Algorithms and Data Structures, with Ap-
plications to Graphics and Geometry. Prentice-Hall, 1993.
J. Nievergelt. Complexity, algorithms, programs, systems: The shifting
focus. In Proc. ALCOM Workshop on Algorithms: Implementation, Li-
braries, and Use, J. Symbolic Computation, volume 17, pages 297-310,
1994.
• ]firg Nievergelt, Peter Schorn, Michele de Lorenzi, Christoph Ammann,
and Adrian Br/ingger. XYZ: A project in experimental geometric compu-
tation. In Computational Geometry -- Methods, Algorithms and Appli-
cations: Proc. Internato Workshop Comput. Geom. CG '91, volume 553
of Lecture Notes in Computer Science, pages 171-186. Springer-Verlag,
1991.
F. P. Preparata and M. I. Shamos. Computational Geometry: An Intro-
duction. Springer-Verlag, New York, NY, 1985.
P. Schorn. The XYZ GeoBench for the experimental evaluation of geo-
metric algorithms. In DtMA CS Workshop on Computational Support for
Discrete Mathematics, 1992.
M. I. Shamos and D. Hoey. Closest-point problems. In Proc. 16th Annu.
IEEE Sympos. Found. Comput. Sci., pages 151-162, 1975.
P. M. Vaidya. An O(n log n) algorithm for the all-nearest-neighbors prob-
lem. Discrete Comput. Geom., 4:101-115, 1989.
19