The XYZ GeoBench software for geometric computation has been upgraded to version 4.4.3. Starting with this version, the full Object Pascal (THINK Pascal) source code is available for free for non-commercial use only. Commercial users still need to get a license. A summary of changes is at the end of this article. 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) - 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) - 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) 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.3 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 XYZ: XYZDemoData.sea.hqx 64944 (Demo data) XYZGeoBench.sea.hqx 447073 (Program, version 4.4.3) XYZGeoBenchNoFPU.sea.hqx 461696 (Program, no coprocessor needed, slow) XYZGeoBenchSource.sea.hqx 906294 (source code, non-commercial applications only!) XYZImplementation.sea.hqx 272398 (Implementation aspects, MacWrite II) XYZManualWord4.sea.hqx 253942 (Manual 4.4.3, Word 4.0 format) XYZOverview.sea.hqx 269830 (XYZ project overview, MacWrite II) XYZProject.sea.hqx 266404 (XYZ project description, MacWrite II) XYZTestData.sea.hqx 650718 (Test data) readme 6301 (This file) Decoding: Transfer the file using ftp, decode it with BinHex and double click the Self Extracting Archive (.sea). Changes and improvements made in version 4.4.0: * much improved and extended algorithms for triangulations with new operations * improved interactive manipulation of 3-d views * more user selectable preferences * more interactive operations (triangulation, distance of convex polygons, winding number) Changes and improvements made in version 4.4.1: * manual was updated to version 4.4.1 * different result handling modes (new window, add as selection, replace selection, delete result) * modifier keys for temporary change of result handling mode * a couple of new operations * additional user selectable preferences and better documentation * the clipboard may contain textual data * textual data is also written to the clipboard * a simplified textual format for point set data is available * the icon of GeoBench documents was changed requiring a removal of old GeoBench versions * some minor bug fixes Changes and improvements made in version 4.4.2: * manual was updated to version 4.4.2 * new commands for creating random graphs, merging graphs and interactively adding edges to a graph * CABRI graph textual documents can be read * some minor bug fixes and cosmetic changes Changes and improvements made in version 4.4.3: * manual was updated to version 4.4.3 * new algorithms for on-line closest-pair, traveling salesman, Voronoi-diagram * dynamic execution of many operations: drag one object of the configuration and the result is recomputed continuously * improved test data generator for graphs * new data structures: unionFind and infiniteUndirectedGraph * source code released to the public for non-commercial purposes * more general purpose commands (area, perimeter, arrange, convert, etc.) * smoother dragging * the program can compute in the background * numerous minor improvements and bug fixes For further enquiries contact: Peter Schorn Informatik, ETH CH-8092 Zurich schorn@inf.ethz.ch