Abstract We present the software library STXXLthat is an implementation of the C++ standard template library (STL) for processing huge data sets that can fit only on hard disks. It supports parallel disks, overlapping between disk I/O and computation and it is the first I/O‐efficient algorithm library that supports the pipelining technique that can save more than half of the I/Os. STXXLhas been applied both in academic and industrial environments for a range of problems including text processing, graph algorithms, computational geometry, Gaussian elimination, visualization, and analysis of microscopic images, differential cryptographic analysis, etc. The performance of STXXLand its applications are evaluated on synthetic and real‐world inputs. We present the design of the library, how its performance features are supported, and demonstrate how the library integrates with STL. Copyright © 2007 John Wiley & Sons, Ltd.

We present an extension of snap roundingfrom straight-line segments (see Guibas and Marimont, 1998)to Bézier curves of arbitrary degree, and thus the first method for geometric roundingof curvilinear arrangements.Our algorithm takes a set of intersecting Bézier curvesand directly computes a geometric rounding of their true arrangement, without the need of representing the true arrangement exactly.The algorithm's output is a deformation of the true arrangementthat has all Bézier control points at integer pointsand comes with the same geometric guarantees as instraight-line snap rounding: during rounding, objects do not movefurther than the radius of a pixel, and features of thearrangement may collapse but do not invert.

We present an algorithm to enumerate the pointed pseudotriangulations of a given point set, based on the greedy flip algorithm of Pocchiola and Vegter [Discrete Comput. Geom. 16 (1996), pp. 419–453]. Our two independent implementations agree and allow us to experimentally verify or disprove conjectures on the numbers of pointed pseudotriangulations and triangulations of a given point set. (For example, we establish that the number of triangulations is bounded by the number of pointed pseudotriangulations for all sets of up to 10 points.)

We present the first exact, complete and efficient implementation that computes for a given set P=p1,...,pn of quadric surfaces the planar map induced by all intersection curves p1∩ pi, 2 ≤ i ≤ n, running on the surface of p1. The vertices in this graph are the singular and x-extreme points of the curves as well as all intersection points of pairs of curves. Two vertices are connected by an edge if the underlying points are connected by a branch of one of the curves. Our work is based on and extends ideas developed in [20] and [9].Our implementation is complete in the sense that it can handle all kind of inputs including all degenerate ones where intersection curves have singularities or pairs of curves intersect with high multiplicity. It is exact in that it always computes the mathematical correct result. It is efficient measured in running times.

Nef polyhedra in d-dimensional space are the closure of half-spaces under boolean set operation. In consequence, they can represent non-manifold situations, open and closed sets, mixed-dimensional complexes and they are closed under all boolean and topological operations, such as complement and boundary. They were introduced by W. Nef in his seminal 1978 book on polyhedra.We presented in previous work a new data structure for the boundary representation of three-dimensional Nef polyhedra with efficient algorithms for boolean operations. These algorithms were designed for correctness and can handle all cases, in particular all degeneracies. To this extent we rely on exact arithmetic to avoid well known problems with floating-point arithmetic.In this paper, we present important optimizations for the algorithms. We describe the chosen implementations for the point-location and the intersection-finding subroutines, a kd-tree and a fast box-intersection algorithm, respectively. We evaluate this optimized implementation with extensive experiments that supplement the runtime analysis from our previous paper and that illustrate the effectiveness of our optimizations. We compare our implementation with the ACIS CAD kernel and demonstrate the power and cost of the exact arithmetic in near-degenerate situations.The implementation was released as Open Source in the CGAL release 3.1 in December 2004.

The Bentley-Ottmann sweep-line method can be used to compute thearrangement of planar curves provided a number of geometricprimitives operating on the curves are available. We discuss themathematics of the primitives for planar algebraic curves of degreethree or less and derive efficient realizations. As a result, weobtain a complete, exact, and efficient algorithm for computingarrangements of cubic curves. Conics and cubic splines are specialcases of cubic curves. The algorithm is complete in that it handles all possibledegeneracies including singularities. It is exact in that itprovides the mathematically correct result. It is efficient in thatit can handle hundreds of curves with a quarter million of segmentsin the final arrangement.

This video shows a prototype system for the visualization of time-vary ing volume data of one or several variables as they occur in scientific and engineering applications. It partitions the data dimensions on the client side into a 3D viewer for iso-surfaces and a 2D control plane where each point selects a particular iso-surface in 3D.

CGAL is a Computational Geometry Algorithms Library written in C++, which is being developed by research groups in Europe and Israel. The goal is to make the large body of geometric algorithms developed in the field of computational geometry available for industrial application. We discuss the major design goals for CGAL, which are correctness, flexibility, ease-of-use, efficiency, and robustness, and present our approach to reach these goals. Generic programming using templates in C++ plays a central role in the architecture of CGAL. We give a short introduction to generic programming in C++, compare it to the object-oriented programming paradigm, and present examples where both paradigms are used effectively in CGAL. Moreover, we give an overview of the current structure of the CGAL-library and consider software engineering aspects in the CGAL-project. Copyright © 2000 John Wiley & Sons, Ltd.

Design solutions for a program library are presented for combinatorial data structures in computational geometry, such as planar maps and polyhedral surfaces. Design issues considered are genericity, flexibility, time and space efficiency, and ease-of-use. We focus on topological aspects of polyhedral surfaces. Edge-based representations for polyhedrons are evaluated with respect to the design goals. A design for polyhedral surfaces in a halfedge data structure is developed following the generic programming paradigm known from the Standard Template Library STL for C++. Connections are shown to planar maps and face-based structures managing holes in facets. 1 Introduction Combinatorial structures, such as planar maps, are fundamental in computational geometry. In order to use computational geometry in practice, a solid library must provide generic and flexible solutions as one of its fundamental cornerstones. Other design criteria are time and space efficiency. Ease-of-use is necessar...