Convex blocking and partial orders on the plane
Let C={c1,,cn} C = { c 1 ,  , c n } be a collection of disjoint closed bounded convex sets in the plane. Suppose that one of them, say c1 c 1 , represents a valuable object we want to uncover, and we are allowed to pick a direction ??[0,2?) ? ? [ 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 ? 0 such that the number of elements that have to be removed along ?0 ? 0 before we can remove c1 c 1 is minimized. We prove that if we have the sorted set D D of directions defined by the tangents between pairs of elements of C , we can find ?0 ? 0 in O(n2) O ( n 2 ) time. We also discuss the problem of sorting D D in o(n2log?n) o ( n 2 log ? n ) time.
convex blocking partial orders dual space multigraphs algorithms