CSC 543

We finished talking about MLPQ and began studying computational geometry. The book has an extensive chapter on computational geometry, which I have supplemented with material from de Berg, van Kreveld, Overmars, Schwarzkopf, Computational Geometry, Springer, 2000. 1d range searching and kd-trees are from Sections 5.1/5.2 of that book. Interval trees are covered in Section 10.1, as is the windowing problem we discussed (including the correct final punchline, which is kd-trees (page 217/218), I will go over this again next week). Interval trees are also covered in our textbook (5.2.4).

**Submission**: you can submit the homework by hardcopy
in class or by sending it to me as an email.

1. [Interval Trees, 20pt] a) Build an interval tree for the following scientists:

- Brahe (1546-1601)
- Bacon (1561-1626)
- Galileo (1564-1642)
- Descartes (1596-1650)
- Halley (1656-1742)
- Leibniz (1646-1716)
- Fahrenheit (1686-1736)
- Franklin (1706-1790)
- Newton (1642-1727)
- Laplace (1749-1827)

b) List the scientists alive in the year 1640. Show the details of how the query proceeds.

Note: For the three problems 2-4 below sketch algorithms and data structures you use or build (you do not have to implement any of them or even give pseudocode). The descriptions can be high-level, but should be precise. You can use algorithms/data structures we saw in class.

2. [Far Points on a Line, 10pt] You are given n points X := {x_{1},
…, x_{n}}, on the real line. You want to preprocess them in time
O(n log n) so that you can quickly answer queries of the following type: given
real number x and distance d, find all points in X that have distance at least d
from x. Fast means O(log n + k), where k is the number of points in the output.

3. [Circles in a Rectangle, 15pt] You are given n axis-parallel rectangles in
the plane {R_{1},
…, R_{n}}. You want to preprocess them in time O(n log n) so that you
can quickly list all the rectangles that a given circle (given by center p and
radius r) is fully contained in. Quickly means time O(log n + k), where k is the
number of rectangles in the output. (Why does this problem get much harder if
instead of "contained in" we require "intersects"?)

4. [Visibility Problem, 15pt] You have a camera located at the origin of the coordinate system (0,0). The lens has a viewing angle of 45º and can be turned into any direction by specifying a rotation angle between 0º (looking east along the x-axis) and 360º. In the plane there are n points. For any specified rotation angle we want to list all the points that the camera can see. The preprocessing of the n input points in time should take time O(n log n) and each resetting of the camera angle O(log n + k), where k is the number of points that are visible at the new angle.

5. [Extra Credit] In the 4-intersection model for arcs on a circle (from the midterm), there is at least one scenario which has two essentially different realizations by arcs (different in how the exterior of the arcs intersect arc boundary/interior/exterior). Find such a case and show the different realizations.

Marcus Schaefer

Last updated: May 13th, 2009.