Abstract Voronoi Diagrams (avd)

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.

home: http://www.mpi-sb.mpg.de/LEDA/friends/avd.html

Curve Reconstruction Algorithms (CR)

This LEP implements algorithms for curve reconstruction.

home: http://www.mpi-sb.mpg.de/~althaus/LEP:Curve-Reconstruction/curve.html

D-Dimensional Geometry (dd_geokernel)

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.

home: http://www.mpi-sb.mpg.de/LEDA/friends/dd_geokernel.html

Dynamic Graph Algorithms (dynamic_graphs)

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.

home: http://www.mpi-sb.mpg.de/LEDA/friends/dyngraph.html

Extended Geometry (extgeo)

This LEP implements the overlay of segments, rays, and lines by a generic sweep method that is based on an extension of affine geometry. 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.

home: http://www.mpi-sb.mpg.de/LEDA/friends/extgeo.html

Geometry LEDA Extension Package (GEOMLEP)

The GEOMLEP (Geometry LEDA Extension Package) package consists of a number of algorithms and data structures from the field of Computational Geometry that complete and enhance the algorithms and data structures provided by the LEDA library. GEOMLEP also provides additional classes for visualization that can be used together with the GeoWin visualization tool of LEDA.

home: http://www.mpi-sb.mpg.de/LEDA/friends/geomlep.html

Graph Iterators

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.

home: http://www.mpi-sb.mpg.de/LEDA/friends/git.html

LEDA-in-the-Web TransWire (transwire)

LEDA-in-the-Web TransWire is a library, consisting of a Java portion and a C++ portion. It can be used to implement client-server applications where the server is written in C++ and the client in Java.

home: http://www.mpi-sb.mpg.de/LEDA/friends/ledainweb.html

Parametric Search (paramsearch)

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.

home: http://www.mpi-sb.mpg.de/LEDA/friends/paramsearch.html

SD-Trees (sd_tree)

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.

home: http://www.mpi-sb.mpg.de/LEDA/friends/SD_Tree.html

Sphere Geometry (SphereGeometry)

This LEP implements objects on the unit sphere (like points, great arcs, hemispheres, polygons, etc.) using an implicit representation.

home: http://www.mpi-sb.mpg.de/LEDA/friends/SphereGeometry.html

KCUT (KCUT)

Given an undirected Graph G with non-negative edge weights, this LEP computes a minimum k-cut; that is a set C of edges such that G\C has at least k components and in addition the sum of the weight of the edges in C is minimized.

home: http://www.mpi-sb.mpg.de/LEDA/friends/KCUT.html

Minimum Mean Cycle (MinMeanCycle)

Given a directed Graph G where each edge has a weight c(e); this LEP computes a minimum mean cycle C for G; that is a cycle C that minimizes c(C)/|C|.

home: http://www.mpi-sb.mpg.de/LEDA/friends/MinimumMeanCycle.html

LEDA GraphML LEP

GraphML is a comprehensive and easy-to-use file format for graphs. LEDA GraphML is an extension package for GraphML developed by the GraphML project.

home: http://graphml.graphdrawing.org/

Rank-Maximal Matchings LEP

Given a bipartite graph G((A,B),E), and a partition of the edge set into at most n disjoint sets (called ranks), the LEP computes a matching M such that it contains the maximum number of rank 1 edges and, given that constraint, the maximum number of rank 2 edges and so on.

home: http://www.mpi-sb.mpg.de/~michail/rmm.shtml

Minimum Cycle Basis LEP

A minimum cycle basis is a basis of the cycle space of a graph with minimum weight. The weight of a minimum cycle basis is the sum of the weights of its cycles and the weight of a cycle is the sum of the weights of its edges. This package contains implementations of algorithms to compute minimum cycle bases for weighted directed and undirected graphs.

home: http://www.mpi-inf.mpg.de/~michail/mcb.shtml