A generalization of the convex Kakeya problem

DOI10.1007/978-3-642-29344-3_1zbMATH Open1314.52002arXiv1209.2171OpenAlexW1833243817MaRDI QIDQ486985FDOQ486985

Otfried Cheong, Sang Won Bae, Joachim Gudmundsson, Hee-Kap Ahn, Takeshi Tokuyama, Antoine Vigneron

Publication date: 19 January 2015

Published in: Algorithmica, LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

Abstract: 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 Theta(n log n)-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.

Full work available at URL: https://arxiv.org/abs/1209.2171

Recommendations

• A generalization of the convex Kakeya problem
• The Fat Needle Problem
• Aligning two convex figures to minimize area or perimeter
• The reverse Kakeya problem
• The reverse Kakeya problem

zbMATH Keywords

algorithmscomputational geometryKakeya problem, convex sets

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55) Convex sets in (2) dimensions (including convex curves) (52A10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the densest packing of convex discs
• Title not available (Why is that?)
• Sets of constant width
• Title not available (Why is that?)
• Title not available (Why is that?)
• The minimum mean width translation cover for sets of diameter one
• Aligning two convex figures to minimize area or perimeter
• Extremalprobleme für konvexe Bereiche der euklidischen Ebene
• From rotating needles to stability of waves: emerging connections between combinatorics, analysis, and PDE
• Sectorial Covers for Curves of Constant Length
• Covering Curves by Translates of a Convex Set
• Maximum area with Minkowski measures of perimeter
• From harmonic analysis to arithmetic combinatorics
• On a Problem of Besicovitch
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Kakeya Problem
• Title not available (Why is that?)
• On Fundamental Geometric Properties of Plane Line-Sets

Cited In (7)

• Smallest universal covers for families of triangles
• Universal convex covering problems under translations and discrete rotations
• Krein-Milman-type problems for compact matricially convex sets
• Scandinavian thins on top of cake: new and improved algorithms for stacking and packing
• Convex optimisation-based methods for K-complex detection
• On the convexity of general inverse \(\sigma_k\) equations
• A Further Generalized Kettele Algorithm with Multiple Constraints

This page was built for publication: A generalization of the convex Kakeya problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q486985)