Convex blocking and partial orders on the plane

Full Text
Convex-blocking.pdf embargoed access
Request a copy
When filling the form you are requesting a copy of the article, that is deposited in the institutional repository (DUGiDocs), at the autor or main autor of the article. It will be the same author who decides to give a copy of the document to the person who requests it, if it considers it appropriate. In any case, the UdG Library doesn’t take part in this process because it is not authorized to provide restricted articles.
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 alpha is an element of [0, 2 pi) 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 alpha(0) such that the number of elements that have to be removed along alpha(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 alpha(0) in O(n(2)) time. We also discuss the problem of sorting D, in o(n(2)logn) time ​
​Tots els drets reservats