Canadian Mathematical Society
Canadian Mathematical Society
  location:  Publicationsjournals
Search results

Search: MSC category 52C15 ( Packing and covering in $2$ dimensions [See also 05B40, 11H31] )

  Expand all        Collapse all Results 1 - 3 of 3

1. CMB 2009 (vol 52 pp. 424)

Martini, Horst; Spirova, Margarita
Covering Discs in Minkowski Planes
We investigate the following version of the circle covering problem in strictly convex (normed or) Minkowski planes: to cover a circle of largest possible diameter by $k$ unit circles. In particular, we study the cases $k=3$, $k=4$, and $k=7$. For $k=3$ and $k=4$, the diameters under consideration are described in terms of side-lengths and circumradii of certain inscribed regular triangles or quadrangles. This yields also simple explanations of geometric meanings that the corresponding homothety ratios have. It turns out that basic notions from Minkowski geometry play an essential role in our proofs, namely Minkowskian bisectors, $d$-segments, and the monotonicity lemma.

Keywords:affine regular polygon, bisector, circle covering problem, circumradius, $d$-segment, Minkowski plane, (strictly convex) normed plane
Categories:46B20, 52A21, 52C15

2. CMB 2009 (vol 52 pp. 451)

Pach, János; Tardos, Gábor; Tóth, Géza
Indecomposable Coverings
We prove that for every $k>1$, there exist $k$-fold coverings of the plane (i) with strips, (ii) with axis-parallel rectangles, and (iii) with homothets of any fixed concave quadrilateral, that cannot be decomposed into two coverings. We also construct for every $k>1$ a set of points $P$ and a family of disks $\cal D$ in the plane, each containing at least $k$ elements of $P$, such that, no matter how we color the points of $P$ with two colors, there exists a disk $D\in{\cal D}$ all of whose points are of the same color.

Categories:52C15, 05C15

3. CMB 1999 (vol 42 pp. 380)

Nurmela, Kari J.; Östergård, Patric R. J.; aus dem Spring, Rainer
Asymptotic Behavior of Optimal Circle Packings in a Square
A lower bound on the number of points that can be placed in a square of side $\sigma$ such that no two points are within unit distance from each other is proven. The result is constructive, and the series of packings obtained contains many conjecturally optimal packings.

Keywords:asymptotic bound, circle packing

© Canadian Mathematical Society, 2014 :