Given a set of n points P in the plane, we define a subdivision of the plane int
ID: 3679413 • Letter: G
Question
Given a set of n points P in the plane, we define a subdivision of the plane into rectangular regions by the following rule. We assume that all the points are contained within a bounding rectangle. Imagine that the points are sorted in increasing order of y-coordinate. For each point in this order, shoot a bullet to the left, to the right and up until it hits an existing segment, and then add these three bullet-path segments to the subdivision. (See the figure below left for an example.)
1. Show that the resulting subdivision has size O(n) (including vertices, edges, and faces).
2. Describe an algorithm to add a new point to the subdivision and restore the proper subdivision structure. Note that the new point may have an arbitrary y-coordinate, but the subdivision must be updated as if the points were inserted in increasing order of y-coordinate. (See the figure above center and right.)
3. Prove that if the points are added in random order, then the expected number of structural changes to the subdivision with each insertion is O(1).
NO CODE please.
Explanation / Answer
3. Prove that if the points are added in random order, then the expected number of structural changes to the subdivision with each insertion is O(1).
Solution:
If the points are added into random order that means consider insertion of ith segment and k denote the number of exisiting walls that ith segment intersects.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.