Name
Abstract | ||
|---|---|---|
Let C={c1,…,cn} be a collection of disjoint closed bounded convex sets in the plane. Suppose that one of them, say c1, represents a valuable object we want to uncover, and we are allowed to pick a direction α∈[0,2π) 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 α0 such that the number of elements that have to be removed along α0 before we can remove c1 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 α0 in O(n2) time. We also discuss the problem of sorting D in o(n2logn) time. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.comgeo.2015.08.003 | Computational Geometry |
Keywords | Field | DocType |
Convex blocking,Partial orders,Dual space,Multigraphs,Algorithms | Discrete mathematics,Combinatorics,Disjoint sets,Dual space,Sorting,Regular polygon,Tangent,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
51 | C | 0925-7721 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| José Miguel Díaz-Báñez | 1 | 193 | 26.65 |
| Marco A. Heredia | 2 | 17 | 3.65 |
| Canek Peláez | 3 | 1 | 1.06 |
| Joan Antoni Sellarès | 4 | 35 | 8.22 |
| Jorge Urrutia | 5 | 1064 | 134.74 |
| Inmaculada Ventura | 6 | 102 | 10.56 |