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.

  • $\begingroup$ Also check wikipedia... en.wikipedia.org/wiki/Fractional_cascading $\endgroup$ – Sariel Har-Peled Apr 3 '15 at 2:24
  • $\begingroup$ 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. $\endgroup$ – Sariel Har-Peled Apr 3 '15 at 2:32

Chazelle and Guibas wrote a paper describing some of the good applications that can be made with Fractional Cascading: Link

Some of the most interesting applications are:

  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.
  3. Planar point Location. Locate a point in a planar subdivision.

You do have to give a bit more background as this problems tend to be geometrical in nature. Fractional Cascading is really only good when tackling higher dimensional problems.

  • $\begingroup$ The question asks for applications other than the ones "in the original companion paper". I think you have linked to and summarized that paper. $\endgroup$ – jbapple Mar 3 '15 at 13:01
  • $\begingroup$ My apologies. I failed to have notice this. I am unfamiliar with this site, should I remove my answer, or just leave it? $\endgroup$ – S. Pek Mar 3 '15 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.