Convex blocking and partial orders on the plane
2016
Let C = { c 1 , � , c n } be a collection of disjoint closed bounded convex sets in the plane. Suppose that one of them, say c 1 , represents a valuable object we want to uncover, and we are allowed to pick a direction α � 0 , 2 π ) along which we can translate (remove) the elements of C, one at a time, while avoiding collisions. We study the problem of finding a direction α 0 such that the number of elements that have to be removed along α 0 before we can remove c 1 is minimized. We prove that if we have the sorted set D of directions defined by the tangents between pairs of elements of C, we can find α 0 in O ( n 2 ) time. We also discuss the problem of sorting D in o ( n 2 log � n ) time.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
17
References
1
Citations
NaN
KQI