| Leda Extension Packages |
-
LEDA
extension packages (LEPs) extend LEDA into particular
application domains and areas of algorithmics not covered by the
core system. For issues concerning the core system please visit
the
academic program of Algorithmic Solutions Software
GmbH or
contact AS by email.
This LEP implements the construction of a class of Voronoi diagrams called Abstract Voronoi Diagrams. At first it provides a framework which can be used to calculate Abstract Voronoi Diagrams in the plane. To get a program which calculates a concrete type of Voronoi diagram the user has to implement some basis operations which allow the adaptation of the framework to the concrete geometry of the problem. The framework is already adapted to the problem of Euclidean Voronoi diagram of points and line segments in the plane.
This LEP implements algorithms for curve reconstruction.
This LEP implements the basic data types of higher-dimensional computational geometry:points, vectors, directions, hyperplanes, segments, rays, lines, spheres, affine transformations, and operations connecting these types. All geometric primitives are exact , i.e., they do not incur rounding error (because they are implemented using rational arithmetic) and always produce the correct result.
A dynamic graph algorithm is modeled in form of a data structure operating on a graph supporting two types of operations:updates and queries. An update is a local change of the graph and a query is a question about a certain property of the current graph. The aim of such a data structure is to use structural information about the current graph in order to handle an update faster than by the obvious solution, that is recomputing everything from scratch with a static algorithm.
This LEP implements an extension to planar affine geometry. This allows the overlay of segments, rays, and lines by a generic sweep method. We treat affine and points and ray tips abstractly as the endpoints of extended segments. Thereby the generic plane sweep algorithm of LEDA can be used to calculate arrangements of such objects.
Graph iterators propose a method for decoupling graph data graphs in an arbitrary order. Data accessors are introduced objects (node or edge) from the actual algorithms. This LEP allows users to work with LEDA datatypes according to the ideas of STL. There are several example algorithms implemented in this paradigm.
This LEP implements an algorithm that computes the minimum diameter of a set of moving points. The implementation uses parametric search, and solves the problem exactly.
SD-trees implement a data structure which provides nearest-neighbour- and other kinds of search algorithms on static sets of points in two-dimensional space with euclidean distances. The data structure of the binary search tree allows to execute these searches in amortised constant time.