Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k -th root operations for integral k , and taking roots of polynomials whose coefficients are given by the values of subexpressions. We consider the sign computation of real algebraic expressions, a task vital for the implementation of geometric algorithms. We prove a new separation bound for real algebraic expressions and compare it analytically and experimentally with previous bounds. The bound is used in the sign test of the number type leda::real .

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.

We show that the combination of the CGAL framework for geometric computation and the number type ledareal yields easy-to-write, correct and efficient geometric programs.

A program checker verifies that a particular program execution is correct. We give simple and efficient program checkers for some basic geometric tasks. We report about our experiences with program checking in the context of the LEDA system. We discuss program checking for data structures that have to rely on user-provided functions.

In this paper we describe and discuss a kernel for higher-dimensional computational geometry and we present its application in the calculation of convex hulls and delaunay triangulations.We introduce the basic data types like points, vectors, directions, hyperplanes, segments, rays, lines, spheres, affine transformations, and operations connecting these types.The description consists of a motivation for the basic class layout as well as topics like layered software design, runtime correctness via checking routines and documentation issues.Finally we shortly describe the usage of the kernel in the application domain.

Article Computing the minimum diameter for moving points: an exact implementation using parametric search Share on Authors: Jörg Schwerdt Fakultät für Informatik, Otto-von-Guericke-Universität, Magdeburg, Universitätsplatz 2, D-39106 Magdeburg, Germany Fakultät für Informatik, Otto-von-Guericke-Universität, Magdeburg, Universitätsplatz 2, D-39106 Magdeburg, GermanyView Profile , Michiel Smid Fakultät für Informatik, Otto-von-Guericke-Universität, Magdeburg, Universitätsplatz 2, D-39106 Magdeburg, Germany Fakultät für Informatik, Otto-von-Guericke-Universität, Magdeburg, Universitätsplatz 2, D-39106 Magdeburg, GermanyView Profile , Stefan Schirra Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, Germany Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, GermanyView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 466–468https://doi.org/10.1145/262839.263087Online:01 August 1997Publication History 6citation275DownloadsMetricsTotal Citations6Total Downloads275Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A program checker verifies that a particular program execution is correct.We give simple and efficient program checkers for some basic geometric tasks.We report about our experiences with program checking in the context of the LEDA system.We discuss program checking for data structures that have to rely on userprovided functions.

No abstract available.

No abstract available.

Approximate decision algorithms for point set congruence

We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have running time Ω(n2) where n is the number of obstacle corners. We introduce the tightness of a motion planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with running time ο((a/b · 1/ε crit + 1)n(log n)2), where a ≥ b are the lengths of the sides of a rectangle and εcrit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary of n bow-ties (c.f. Figure 1.1) is Ο(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.