TY - JOUR

T1 - A generalization of the convex Kakeya problem

AU - Ahn, Heekap

AU - Bae, Sangwon

AU - Cheong, Otfried

AU - Gudmundsson, Joachim

AU - Tokuyama, Takeshi

AU - Vigneron, Antoine E.

N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: H.-K.A. was supported by NRF grant 2011-0030044 (SRC-GAIA) funded by the government of Korea. J.G. is the recipient of an Australian Research Council Future Fellowship (project number FT100100755). S.W. Bae was supported by NRF grant (NRF-2013R1A1A1A05006927) funded by the government of Korea. O.C. was supported in part by NRF grant 2011-0030044 (SRC-GAIA), and in part by NRF grant 2011-0016434, both funded by the government of Korea.

PY - 2013/9/19

Y1 - 2013/9/19

N2 - Given a set of line segments in the plane, not necessarily finite, what is a convex region of smallest area that contains a translate of each input segment? This question can be seen as a generalization of Kakeya's problem of finding a convex region of smallest area such that a needle can be rotated through 360 degrees within this region. We show that there is always an optimal region that is a triangle, and we give an optimal Θ(nlogn)-time algorithm to compute such a triangle for a given set of n segments. We also show that, if the goal is to minimize the perimeter of the region instead of its area, then placing the segments with their midpoint at the origin and taking their convex hull results in an optimal solution. Finally, we show that for any compact convex figure G, the smallest enclosing disk of G is a smallest-perimeter region containing a translate of every rotated copy of G. © 2013 Springer Science+Business Media New York.

AB - Given a set of line segments in the plane, not necessarily finite, what is a convex region of smallest area that contains a translate of each input segment? This question can be seen as a generalization of Kakeya's problem of finding a convex region of smallest area such that a needle can be rotated through 360 degrees within this region. We show that there is always an optimal region that is a triangle, and we give an optimal Θ(nlogn)-time algorithm to compute such a triangle for a given set of n segments. We also show that, if the goal is to minimize the perimeter of the region instead of its area, then placing the segments with their midpoint at the origin and taking their convex hull results in an optimal solution. Finally, we show that for any compact convex figure G, the smallest enclosing disk of G is a smallest-perimeter region containing a translate of every rotated copy of G. © 2013 Springer Science+Business Media New York.

UR - http://hdl.handle.net/10754/562979

UR - http://arxiv.org/abs/arXiv:1209.2171v1

UR - http://www.scopus.com/inward/record.url?scp=84905570337&partnerID=8YFLogxK

U2 - 10.1007/s00453-013-9831-y

DO - 10.1007/s00453-013-9831-y

M3 - Article

SN - 0178-4617

VL - 70

SP - 152

EP - 170

JO - Algorithmica

JF - Algorithmica

IS - 2

ER -