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

DOI10.1007/978-3-642-40328-6_8zbMATH Open1323.05030arXiv1405.3950OpenAlexW2952407455MaRDI QIDQ747571FDOQ747571

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)

Abstract: For two planar convex bodies, $C$ and $D$, consider a packing $S$ of $n$ positive homothets of $C$ contained in $D$. We estimate the total perimeter of the bodies in $S$, denoted $mper(S)$, in terms of $mper(D)$ and $n$. When all homothets of $C$ touch the boundary of the container $D$, we show that either $mper(S)=O(logn)$ or $mper(S)=O(1)$, depending on how $C$ and $D$ "fit together," and these bounds are the best possible apart from the constant factors. Specifically, we establish an optimal bound $mper(S)=O(logn)$ unless $D$ is a convex polygon and every side of $D$ is parallel to a corresponding segment on the boundary of $C$ (for short, $D$ is emph{parallel to} $C$). When $D$ is parallel to $C$ but the homothets of $C$ may lie anywhere in $D$, we show that $mper(S)=O((1+mesc(S))logn/loglogn)$, where $mesc(S)$ denotes the total distance of the bodies in $S$ from the boundary of $D$. Apart from the constant factor, this bound is also the best possible.

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

Recommendations

• On the total perimeter of homothetic convex bodies in a convex container
• On perimeters of sections of convex polytopes
• On the perimeters of simple polygons contained in a plane convex body
• Upper bounds for the perimeter of plane convex bodies
• On the perimeter of \(k\) pairwise disjoint convex bodies contained in a convex set in the plane
• On the monotonicity of perimeter of convex bodies
• A note on the convex hull of sets of finite perimeter in the plane
• Enclosing a convex body by homothetic bodies
• A sharp quantitative estimate for the perimeters of convex sets in the plane
• The perimeter of rounded convex planar sets

zbMATH Keywords

approximation algorithmconvex bodyperimetermaximum independent settraveling salesmanFord diskshomothet

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Constant-Factor Approximation for TSP with Disks
• On the perimeter of \(k\) pairwise disjoint convex bodies contained in a convex set in the plane
• On the perimeters of simple polygons contained in a plane convex body
• On the total perimeter of homothetic convex bodies in a convex container

This page was built for publication: On the total perimeter of homothetic convex bodies in a convex container

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