Space-efficient geometric algorithms and data structures

By Ilya Katz and Hervé Brönnimann

This is a C++ template library (a la STL, pure source and no linking) that provides several space-efficient data structures for computational geometry. We offer several data structures:

Dictionary is a data structure that supports INSERT, DELETE, and FIND methods. These are attempts to create space efficient dictionaries with manageable running times of the three major operations [detailed documentation]
- beap: bi-parental heap is a data structure that is similar to a heap but has a property that each element has two parents whose values are smaller than the element itself. Here is a space efficient implementation that requires no extra memory besides the data elements and the size of the problem. This data structure supports the basic methods of a dictionary and provides a few other useful functionalities [intro]
- beap_set: - wrapper for the beap
- dynamic_sorted_vector: sorted vector broken down into substructures to allow reasonable modification times
Geometric data structures and algorithms concentrate on several well known problems in the computational geometry community [detailed documentation]
- cgl - small geometry kernel that is sufficient for the needs of the data structures and algorithms of this project.
- kd-trees for points in two dimensions: kd-trees are a data structure to answer window queries (which points are contained in a given query axis-aligned rectangle). This is an inplace static implementation: The points are stored in an array and reordered to encode a kd-tree. There is thus no extra storage for the data structure. Insertion and deletion is not supported. The extra storage for the query function is only for a recursion stack and for storing the answer. [intro]
- dynamic kd-tree: dynamic version of the space efficient kd-tree
- tree/heap - A structure that represents combination of tree and heap data structure
- segment intersection - Another attempt at implementing a space efficient segment intersection algorithm based on sweep line approach using the tree/heap structure presented above

Thesis that describes all of the above algorithms in detail, with references, further suggestions and etc is here [pdf][ps]

All documentation for this project is made with