Given a set {h_1, h_2, ..., h_n} of n halfplanes, the two-dimensional linear pro

Question

Given a set {h_1, h_2, ..., h_n} of n halfplanes, the two-dimensional linear programming problem is to find the "lowest" point in the feasible region. Recall that we studied an incremental algorithm to solve this problem, where the halfplanes are inserted one by one, and the optimal vertex is updated at each step. Briefly explain why the order of insertion of the halfplanes affects the runtime of the algorithm. Consider an edge e in a subdivision, where the two incident faces are triangles. Give the DCEL modifications to perform the operation shown below in Figure 1 (called an edge flip). You do not need to change the face or vertex information, just the next and previous pointers for the edges of the subdivision. Note that the next and prev information changes not only for e, but also for the other four edges that bound the two triangles. Call these edges a, b, c and d. It will be easier to make all the changes by first setting some variables to those edges. In the first homework assignment, you were asked to give an O(log n) time algorithm to determine if a query point q lies inside a convex n-gon whose vertices are given to you in clockwise order. Here, you are asked a similar question about x-monotone polygons: Suppose you are given the vertices {p_1, p_2, ..., P_n} of an x-monotone n-gon P listed in clockwise order (with p_1 as the leftmost vertex). We would like to efficiently answer point location queries of the following form: Given a point q, does it lie inside or outside P? (If q lies on the boundary, it is said to be inside.) Give an 0(log n) time algorithm to answer such queries.

Explanation / Answer

5)

when we want to flip edge, then it may touch more than or equal to 2 vertices.
Then draw circle touching all vertices. Then it will create triangles. Then check vertex of polygon
whether lies on oppsite side of edge. If this particular edge fails to incircle test , then swap edge.
So these edges are actual pointers to DCEL.

Add(M):
find triangles which contains M
then add edges Ma, MB, Mc ...
checkIncircleTest(ab);
checkIncircleTest(bc);
..
.
.

checkIncircleTest(AB)
if(AB is edge on exterior face) then return
Assume e is vertex to right of edge ab;
if(incircle(M,a,b,c,d))
flip edge AB for Ma;
checkIncircleTest(AM);
checkIncircleTest(MB);

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.