Given a set of n points P in the plane, we define a subdivision of the plane int
ID: 3864215 • 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.) Show that the resulting subdivision has size O(n) (including vertices, edges, and faces). 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.)Explanation / Answer
1.
To prove the space bound of O(n), observe that the number of new nodes added to the structure with each new
segment is proportional to the number of newly created subdiviion. In the 3rd problem we proved that with each new
insertion, the expected number of subdiviion that were created was O(1). Therefore, we add O(1) new nodes
with each insertion in the expected case, implying that the total size of the data structure is O(n).
2.
Insert(p) {
Find the triangle abc containing p;
Insert edges pa, pb, and pc into triangulation;
SwapTest(ab); // check/fix the surrounding edges
SwapTest(bc);
SwapTest(ca);
}
SwapTest(ab) {
if (ab is an edge on the exterior face) return;
Let d be the vertex to the right of edge ab;
if (inCircle(p, a, b, d) { // d violates the incircle test
Flip edge ab for pd;
SwaptTest(ad); // check/fix the new suspect edges
SwaptTest(db);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.