Item


Convex blocking and partial orders on the plane

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 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

Elsevier

Manager: Ministerio de Ciencia e Innovación (Espanya)
Author: Diaz-Banez, José Miguel
Heredia, Marco A.
Pelaez, Canek
Sellarès i Chiva, Joan Antoni
Urrutia, Jorge
Ventura, Inmaculada
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
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
Document access: http://hdl.handle.net/2072/297273
Language: eng
Publisher: Elsevier
Rights: Tots els drets reservats
Subject: Algorismes
Algorithms
Conjunts convexos
Convex sets
Title: Convex blocking and partial orders on the plane
Type: info:eu-repo/semantics/article
Repository: Recercat

Subjects

Authors