On the total perimeter of homothetic convex bodies in a convex container

DOI10.1007/s13366-014-0219-1zbMath1323.05030arXiv1405.3950MaRDI QIDQ747571

Adrian Dumitrescu, Csaba D. Tóth

Publication date: 16 October 2015

Published in: Beiträge zur Algebra und Geometrie, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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

zbMATH Keywords

traveling salesman; approximation algorithm; convex body; maximum independent set; perimeter; Ford disks; homothet

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C27: Combinatorial optimization

52C15: Packing and covering in (2) dimensions (aspects of discrete geometry)

68W25: Approximation algorithms

05B40: Combinatorial aspects of packing and covering

52C26: Circle packings and discrete conformal geometry

Related Items

Constant-Factor Approximation for TSP with Disks

Cites Work

• Unnamed Item
• Unnamed Item
• Minimum weight convex Steiner partitions
• Apollonian circle packings: Geometry and group theory. I: The Apollonian group
• Upper bounds for the perimeter of plane convex bodies
• The Strong Dodecahedral Conjecture and Fejes Tóth’s Conjecture on Sphere Packings with Kissing Number Twelve
• Research Problems in Discrete Geometry
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Approximation algorithms for TSP with neighborhoods in the plane
• ON A STRONG VERSION OF THE KEPLER CONJECTURE
• A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
• TSP with neighborhoods of varying size
• The Traveling Salesman Problem for Lines, Balls and Planes