1991/01/01 by Michael Formann, Frank Olaf Wagner · 3 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Optimization and Packing Problems #Lettering #Citation #Berlin wall #Computer science #Library science #Operations research #Computer graphics (images) #Mathematics #Art history #History #Fall of man #Political science
paper · doi:10.1145/109648.109680
openalex publication_date 1991/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
The following packing problem arises in connection with lettering of maps: Given n distinct points pl, p2,.... pn in the plane, determine the supremum uoPi of all reals U, such that there are n pan-wise dtsjomt, axis-parallel, closed squares Ql, Q2,.... Qn of side-length u, where each pi ts a corner of Qi. Note that — by using afine transformation — the problem is equivalent to the case when we want largest homothetic cop~es of a jized rectangle or parallelogram tnstead of equal ly-szzed squares. In the cartographic application, the points are items (groundwater-drillho les etc.) and the squares are places for labels associated with these items (sulphate concentration etc.). An algorithm is presented, that in O(n log n] time either produces a solution, that is guaranteed to be at least half as large as the supremum. This is optimal, m the sense that the corresponding decision problem is NP-complete, no po[ynomzal approximation algorithm with a guaranteed factor ezceedmg ~ exwts, provided that P # AfP; and there M also a lower bound of C2(n log n) for the running time. 1