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.

Combinatorial and geometric computing is a core area of computer science (CS). In fact, most CS curricula contain a course in data structures and algorithms. The area deals with objects such as graphs, sequences, dictionaries, trees, shortest paths, flows, matchings, points, segments, lines, convex hulls, and Voronoi diagrams and forms the basis for application areas such as discrete optimization, scheduling, traffic control, CAD, and graphics. There is no standard library of the data structures and algorithms of combinatorial and geometric computing. This is in sharp contrast to many other areas of computing. There are, for example, packages in statistics (SPSS), numerical analysis (LINPACK, EISPACK), symbolic computation (MAPLE, MATHEMATICA), and linear programming (CPLEX).

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.

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.

A game on trees that is related to the dictionary problem is considered. There are two players, A and B, which take turns. Player A models the user of the dictionary and player B models the implementation of it. At his turn, player A modifies the tree by adding new leaves and player B modifies the tree by replacing subtrees. The cost of an insertion is the depth of the new leaf, and the cost of an update is the size of the subtree replaced. The goal of player A is to maximize cost and the goal of B is to minimize it. It is shown that there is a strategy for player A, which forces a cost of $\Omega (n \log \log n)$ for an n-game, i.e., a game in which each player takes n turns, and that there is a strategy for player B, which keeps the cost within $O(n \log \log n)$.

The work of F.M. Maley (Proc. Chapel Hill Conf. on VLSI, p.261-83, 1985) on \none-dimensional compaction with automatic jog insertion is refined. More \nprecisely, an algorithm with running time O((n2+k)log n), where k=O(n3) is a \nquantity which measures the difference between the input and output sketch, is \ngiven, and Maley's O(n4) algorithm is improved. The compaction algorithm takes \nas input a layout sketch, the wires in a layout sketch are flexible and only \nindicate the topology of the layout. The compactor minimizes the horizontal \nwidth of the layout while maintaining its routability. The exact geometry of \nthe wires is filled in by a router after compaction

A game on trees, which is related to the dictionary problem is considered. There are two players A and B who take turns. Player A models the user of the dictionary, and player B models its implementation. Player A modifies the tree by adding new leaves, and player B modifies the tree by replacing subtrees. The cost of an insertion is the depth of the new leaf, and the cost of an update is the size of the subtree replaced. The goal of player A is to maximize cost, and the goal of B is to minimize it. It is shown that there is a strategy for player A that forces a cost of Omega (n log log n) for an n-game, that is, a game consisting of n turns of both players, and a strategy for player B that keeps the cost in O(n log log n).>

We prove a Θ(log log n ) (i.e. matching upper and lower) bound on the complexity of the Union-Split-Find problem, a variant of the Union-Find problem. Our lower bound holds for all pointer machine algorithms and does not require the separation assumption used in the lower bound arguments of Tarjan [T79] and Blum [B86]. We complement this with a Θ(log n ) bound for the Split-Find problem under the separation assumption. This shows that the separation assumption can imply an exponential loss in efficiency.

Article Free Access Share on Dynamization of geometric data structures Authors: O. Fries Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West Germany Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West GermanyView Profile , K. Mehlhorn Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West Germany Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West GermanyView Profile , St. Näher Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West Germany Fachbereich 10, Angewandte Mathematik und Informatik, Universitiit des Saarlandes, 6600 Saarbrücked, West GermanyView Profile Authors Info & Claims SCG '85: Proceedings of the first annual symposium on Computational geometryJune 1985 Pages 168–176https://doi.org/10.1145/323233.323256Published:01 June 1985Publication History 24citation262DownloadsMetricsTotal Citations24Total Downloads262Last 12 Months10Last 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 SiteeReaderPDF