This project implements fractional cascading over graphs, as described in "Fractional Cascading I. A Data Structuring Technique" by Chazelle and Guibas (1986).
We also implement two applications from "Fractional Cascading II. Applications":
- Intersecting a Polygonal Path with a Line (Section 3)
- Visualization of hive graph from Orthogonal Range Search (Section 5)
Build the C++ portion of the code via make (requires GCC).
To run the Python visualizations (also spawned by the C++ code), you need the following dependencies:
- NumPy (
pip install numpy) - Matplotlib (
pip install matplotlib)