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:
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 := {x1, …, xn}, 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 {R1, …, Rn}. 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.