DUGiDocsConvex blocking and partial orders on the plane
Text Complet
Convex-blocking.pdf
Sol·licita còpia a l'autor de l'article
En omplir aquest formulari esteu demanant una còpia de l'article dipositat al repositori institucional (DUGiDocs) al seu autor o a l'autor principal de l'article. Serà el mateix autor qui decideixi lliurar una còpia del document a qui ho sol•liciti si ho creu convenient. En tot cas, la Biblioteca de la UdG no intervé en aquest procés ja que no està autoritzada a facilitar articles quan aquests són d'accés restringit.
Compartir
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