Exact Algorithms for a Geometric Packing Problem (Extended Abstract)

Ludek Kucera, Kurt Mehlhorn, B. Preis, Erik Schwarzenecker

Abstract

We investigate the following packing problem: given n points p 1,..., p n in the plane determine the supremum σ opt of all reals σ, for which there are n pairwise disjoint, axis-parallel squares Q 1,..., Q n of side length σ, where for each i, 1 ≤ i ≤ n, p i is a corner of Q i . The problem arises in the connection with lettering of maps, and its decision version is NP-complete. We present two exact algorithms for the decision problem with time complexities 4O(√n) and 4O(√n log n), resp. while the first one is of only theoretical interest because of a large multiplicative factor in the exponent, the other is suitable for practical computation.
BibTeX
@inproceedings{kucera1993exact,
  author = {Ludek Kucera and Kurt Mehlhorn and B. Preis and Erik Schwarzenecker},
  title = {{Exact Algorithms for a Geometric Packing Problem (Extended Abstract)}},
  booktitle = {STACS},
  year = {1993},
  doi = {10.1007/3-540-56503-5\_32},
}

Loading related content...

Figure