Item
Ministerio de Ciencia e InnovaciÃ³n (Espanya)  
DÃazBÃ¡Ã±ez, JosÃ© Miguel
Heredia, Marco A. Pelaez, Canek SellarÃ¨s i Chiva, Joan Antoni Urrutia, Jorge Ventura, Inmaculada 

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 Partially supported by the Spanish Government under Project MEC MTM200908652, and by the ESF EUROCORES program EuroGIGAComPoSe IP04MICINN Project EUIEURC20114306. Partially supported by CONACYT of Mexico. Partially supported by CONACYT of Mexico. Partially supported by the Spanish MCI grant TIN201020590C0202. Partially supported by SEPCONACYT of Mexico, Proyecto 80268, and by the Spanish Government under Project MEC MTM200908652 

application/pdf  
023858  
09257721 (versiÃ³ paper) 1879081X (versiÃ³ electrÃ²nica) 

http://hdl.handle.net/10256/11974  
eng  
Elsevier  
MICINN/PN 20112013/TIN201020590C0202 ReproducciÃ³ digital del document publicat a: http://dx.doi.org/10.1016/j.bspc.2012.12.00310.1016/j.comgeo.2015.08.003 Articles publicats (DIMA) 

Â© Computational Geometry: Theory and Applications, 2016, vol. 51, p. 5566  
Tots els drets reservats  
Algorismes
Algorithms Conjunts convexos Convex sets 

Convex blocking and partial orders on the plane  
info:eurepo/semantics/article  
DUGiDocs 