In class we showed that any triangulation of any n-sided simple polygon has exac
ID: 3864214 • Letter: I
Question
In class we showed that any triangulation of any n-sided simple polygon has exactly n - 2 triangles. Suppose now that the n-sided polygon has m polygonal holes each having k sides. (In the figure above, n = 8, m = 3, and k = 4.). As a function of n, h, and k, how many triangles will such a triangulation have? There exists a set of line segments and a (very nasty) insertion order for these segments so that the depth of the point-location data structure described in class (using trapezoidal decomposition) is Ohm((n) (in case you are not familiar with Ohm notation, this means at least some constant times n). Explain briefly.Explanation / Answer
Answer 7:
Using Euler's Theorem. There are V = (n+hk) vertices, F = t + h + 1 faces, one for each triangle and hole, plus the exterior face, and E = (3t + V)/2 edges, where three per triangle plus the boundary counts each edge twice. Then V — E + F — 2 yields t = n + hk + 2h—2.
Answer 8
The number of new nodes added to the structure with each new segment is proportional to the number of newly created trapezoids. With each new insertion, the expected number of trapezoids that will be created is 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).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.