<p>Chazelle and Guibas wrote a paper describing some of the good applications that can be made with Fractional Cascading: <a href="http://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading2.pdf" rel="nofollow">Link</a></p>

<p>Some of the most interesting applications are:</p>

<ol>
<li>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$.</li>
<li>Orthogonal Range Search. Given points in $R^d$, and a $d$-orthotope. Return the points that lie in the orthotope.</li>
<li>Planar point Location. Locate a point in a planar subdivision.</li>
</ol>

<p>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. </p>

CC BY-SA 3.0
2015-03-03T13:01:22.150Z
The question asks for applications other than the ones "in the original companion paper". I think you have linked to and summarized that paper.
jbapple
CC BY-SA 3.0
2015-03-03T13:02:49.810Z
My apologies. I failed to have notice this. I am unfamiliar with this site, should I remove my answer, or just leave it?
S. Pek
CC BY-SA 3.0
2015-03-03T11:04:39.710Z
2015-03-03T11:04:39.710Z
S. Pek
<p>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.</p>

<p>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.</p>

<p>Any help will be much appreciated.</p>

CC BY-SA 3.0
2015-04-03T02:24:01.417Z
Also check wikipedia... http://en.wikipedia.org/wiki/Fractional_cascading
Sariel Har-Peled
CC BY-SA 3.0
2015-04-03T02:32:40.717Z
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
<ds.data-structures>
Looking for easy applications of fractional cascading
Ari
# Looking for easy applications of fractional cascading

(Asked by: username_0 on 2015-02-25)

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.

**Tags:** ds.data-structures

> **Comments:**
> **username_1**: Also check wikipedia... http://en.wikipedia.org/wiki/Fractional_cascading  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2015-03-03. Score: 1

Chazelle and Guibas wrote a paper describing some of the good applications that can be made with Fractional Cascading: [Link](http://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading2.pdf)

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.

> **Comments:**
> **username_3**: The question asks for applications other than the ones "in the original companion paper". I think you have linked to and summarized that paper.  
> **username_2**: My apologies. I failed to have notice this. I am unfamiliar with this site, should I remove my answer, or just leave it?  

---

