# Looking for easy applications of fractional cascading

I want to give a couple of talks on fractional cascading, one of which will focus on applications. I'm looking for applications that make use of the full version of fractional cascading, not just the simple search-in-k-sorted-lists version.

The applications presented in the original companion paper require a lot of machinery in addition to fractional cascading and are therefore not suitable. My audience is general CS people who don't have specialized data-structures or computational-geometry knowledge.

Any help will be much appreciated.

• Also check wikipedia... en.wikipedia.org/wiki/Fractional_cascading – Sariel Har-Peled Apr 3 '15 at 2:24
• Also, the $O(n \log n)$ time algorithm for computing closest pair of points, can be interpreted as using some form of fractional cascading. Naively, the running time is worse by $O( \log n)$ factor. – Sariel Har-Peled Apr 3 '15 at 2:32

1. Intersection of a polygonal path $P$ and a line. Given the path $P$, pre-process it and allow queries of the form: Given a line $l$, report all the intersections of $P$ and $l$.
2. Orthogonal Range Search. Given points in $R^d$, and a $d$-orthotope. Return the points that lie in the orthotope.