Exact Algorithms for a Geometric Packing Problem (Extended Abstract)
Lists
Only you see this
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...