XYZ Geobench The XYZ GeoBench (eXperimental geometrY Zurich) is a workbench for geometric computation for Macintosh computers (requires the mathematical coprocessor, 4MB of memory, system software 6.0.5 or higher, large screen preferable). It provides an interactive front-end with algorithm animation to the XYZ Program Library that contains many standard algorithms for 2-d problems, several for restricted 3-d problems, and one for d-dimensional computational geometry. The 2-d algorithms currently in the library include: - Convex hull of a point set (Graham's scan, divide and conquer) - Convex hull of a simple polyline (linear time algorithm) - Diameter, distance and intersection of convex polygons - Tangents common to two convex polygons - Boolean operations (union, intersection, difference) on polygons - Contour of a set of rectangles - Winding number - Point(s) in polygon test (sweep line) - Intersection of line segments (sweep line for the first intersection and for reporting all intersections, sweep line for the special case of horizontal and vertical line segments) - Closest pair of points (sweep line [with heuristic], projection method, divide and conquer, probabilistic) - Closest pair of line segments (sweep line) - Closest pair of convex polygons (sweep line) - All nearest neighbors (sweep line, simplified sweep line, extraction from Voronoi diagram, box shrinking method, projection method) - All nearest neighbors in a sector (sweep line) - Voronoi diagram (sweep line, simplified sweep line) - Euclidean minimum spanning tree (EMST) - Clustering of points using an EMST - Traveling salesman heuristics (nearest neighbor, EMST, convex hull, tour optimizer) - Exact solution to the traveling salesman problem - 2-d tree operations (insert, range query, show partition) - Quad-tree operations (creation, boolean operations) - Lower envelope of a set of line segments - Triangulation of a (monotone) polygon [with holes] (trapezoidal decomposition, sweep line) - Triangulation of a set of points (randomized incremental) - Delaunay Triangulation (from Voronoi-diagram, from arbitrary triangulation by edge-flipping, using a grid) - Smallest area disk enclosing a set of points (randomized incremental, also in d-dimensions) - Test whether an arbitrary polygon is convex - On line closest pair - Calculation of a Henneberg 2-sequence for a graph (randomized) - Clustering of points (EMST) The execution of all algorithms can be animated and experimentation is facilitated by - test data generators (random and degenerate configurations) - exchangeable, parametric arithmetic - exchangeable abstract data types - interfaces to the outside world: cut and paste and a textual format The system is written in Object Pascal (approximately 2.4 MByte source, THINK Pascal V4.0.2). The XYZ GeoBench is not in the public domain, but you can use and distribute it freely for research and teaching. Source code for non-commercial applications is available via anonymous ftp (see below). Source code for commercial applications is available for SFr. 1000 which grants all rights. Availability: Object code, source code for non-commercial applications, and documentation via anonymous ftp from neptune.inf.ethz.ch (129.132.101.33) in directory pub/xyz: XYZDemoData.sea.hqx 72764 (Demo data) XYZEvolution.sea.hqx 60938 (XYZ project evolution, Word 5 format) XYZExperiment.sea.hqx 78780 (experimental results, Word 5 format) XYZGeoBench.sea.hqx 471208 (Program, version 4.4.6) XYZGeoBenchNoFPU.sea.hqx 486326 (Program, no coprocessor needed, slower) XYZGeoBenchSource.sea.hqx 1044701 (source code, non-commercial applications only!) XYZImplementation.sea.hqx 59645 (Implementation aspects, MacWrite Pro) XYZManualWord.sea.hqx 324939 (Manual 4.4.6, Word 5 format) XYZOverview.sea.hqx 248049 (XYZ project overview, MacWrite Pro) XYZProject.sea.hqx 253833 (XYZ project description, MacWrite Pro) XYZTestData.sea.hqx 654212 (Test data) readme 7820 (A file giving an overview) The directory "experimental/" contains a current experimental version of the GeoBench (usually with additional functionality) whereas the directory "papers/" contains postscript versions of papers in connection with the XYZ project. Decoding: Transfer the file using ftp, decode it with BinHex and double click the Self Extracting Archive (.sea). References 1. P. Schorn: The XYZ GeoBench: An object oriented workbench for geometric computation, Proc. Second Canadian Conference on Computational Geometry, Aug. 1990. 2. J. Nievergelt, P. Schorn, M. De Lorenzi, C. Ammann, A. Bruengger: XYZ: A project in experimental geometric computation, LNCS 553, Springer, 171-186, 1991. 3. J. Nievergelt, P. Schorn, M. De Lorenzi, C. Ammann, A. Bruengger: eXperimental geometrY Zurich, Software for Geometric Computation, ETH Technical Report 163, July, 1991. 4. P. Schorn: The XYZ GeoBench: A programming environment for geometric algorithms, LNCS 553, Springer, 187-202, 1991. 5. P. Schorn: Robust Algorithms in a Program Library for Geometric Computation, ETH Dissertation 9519, 1991, appeared also in Verlag der Fachvereine (vdf) Zuerich (ISBN 3 7281 1863 X). 6. P. Schorn, A. Bruengger, M. De Lorenzi: The XYZ GeoBench: Animation of Geometric Algorithms, Video presented at the 8th Annual ACM Symposium on Computational Geometry, Berlin 1992. 7. abstract of (6) in 'Animation of Geometric Algorithms: A Video Review', SRC report 87a, eds. M. H. Brown, J. Hershberger, Palo Alto, June 1992. 8. P. Schorn: The XYZ GeoBench for the experimental evaluation of geometric algorithms, DIMACS Workshop on Computational Support for Discrete Mathematics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 15, 137-151, 1994. 9. P. Schorn: Evolution of a software system: Interaction, Interfaces and Applications in the XYZ GeoBench, J. Symbolic Computation, Volume 17, 311-320, 1994.