Convex blocking and partial orders on the plane
dc.contributor.author
dc.date.accessioned
2016-01-28T09:21:24Z
dc.date.available
2016-01-28T09:21:24Z
dc.date.issued
2016
dc.identifier.issn
0925-7721
dc.identifier.uri
dc.description.abstract
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
dc.description.sponsorship
Partially supported by the Spanish Government under Project MEC MTM2009-08652, and by the ESF EUROCORES program EuroGIGA-ComPoSe IP04-MICINN Project EUI-EURC-2011-4306.
Partially supported by CONACYT of Mexico.
Partially supported by CONACYT of Mexico.
Partially supported by the Spanish MCI grant TIN2010-20590-C02-02.
Partially supported by SEP-CONACYT of Mexico, Proyecto 80268, and by the Spanish Government under Project MEC MTM2009-08652
dc.format.mimetype
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier
dc.relation
info:eu-repo/grantAgreement/MICINN//TIN2010-20590-C02-02/ES/AVANCES EN REALIDAD VIRTUAL PARA APLICACIONES PUNTERAS-UDG/
dc.relation.isformatof
Reproducció digital del document publicat a: http://dx.doi.org/10.1016/j.bspc.2012.12.00310.1016/j.comgeo.2015.08.003
dc.relation.ispartof
© Computational Geometry: Theory and Applications, 2016, vol. 51, p. 55-66
dc.relation.ispartofseries
Articles publicats (D-IMA)
dc.rights
Tots els drets reservats
dc.subject
dc.title
Convex blocking and partial orders on the plane
dc.type
info:eu-repo/semantics/article
dc.rights.accessRights
info:eu-repo/semantics/embargoedAccess
dc.embargo.terms
Cap
dc.date.embargoEndDate
info:eu-repo/date/embargoEnd/2026-01-01
dc.type.version
info:eu-repo/semantics/publishedVersion
dc.identifier.doi
dc.identifier.idgrec
023858
dc.contributor.funder
dc.relation.ProjectAcronym
dc.identifier.eissn
1879-081X