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

DOI10.1007/s13366-014-0219-1zbMath1323.05030arXiv1405.3950OpenAlexW2952407455MaRDI 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 salesmanapproximation algorithmconvex bodymaximum independent setperimeterFord diskshomothet

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Approximation algorithms (68W25) Combinatorial aspects of packing and covering (05B40) Circle packings and discrete conformal geometry (52C26)

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