Efficiently finding all points dominated by a point in 2D
<p>In the OCW <a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/index.htm" rel="nofollow noreferrer">Advanced Data Structures course</a>, Prof. E. Demaine mentions a Data Structure that is able to find all the points dominated by a query point (b<sub>2</sub>, b<sub>3</sub>) using O(n) space and O(k) time, provided that a search for point b<sub>3</sub> has already been completed, where k is the size of the output.</p>

<p>The solution works by transforming the above problem into a ray stabbing problem, and using a technique similar to fractional cascading, as shown in the following <a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/calendar-and-notes/MIT6_851S12_Lec4.pdf" rel="nofollow noreferrer">image from the lecture notes</a>:</p>

<p><a href="https://i.stack.imgur.com/cUqby.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/cUqby.png" alt="Finding all points dominated by (b&lt;sub&gt;2&lt;/sub&gt;, b&lt;sub&gt;3&lt;/sub&gt;)."></a></p>

<p>While the concept itself is intuitive, implementing the actual data structure is not straightforward at all.</p>

<p>Chazelle describes this in a paper as <a href="https://www.cs.princeton.edu/~chazelle/pubs/FilteringSearch.pdf" rel="nofollow noreferrer">Filtering Search (pp712)</a>.</p>

<p>I would like to find additional literature or answers that describe and explain of this data structure and algorithm (perhaps with pseudo code and more images, with focus on implementation).</p>

<p>Additionally, I would also like to know more about whether this structure can be implemented in a way that is not "static".  That is, I would like to be able to insert and delete points from the structure as efficiently as possible.</p>