Approximation algorithms for aligning points

ABSTRACT

We study the problem of aligning as many points as possible horizontally, vertically, or diagonally, when each point is allowed to be placed anywhere in its own, given region. Different shapes of placement regions and different sets of alignment orientations are also considered. More generally, we assume that a graph is given on the points, and only the alignments of points that are connected in the graph count. We show that for planar graphs the problem is NP-hard, and we provide inapproximability results for general graphs. For the case of trees and planar graphs, we give approximation algorithms whose performance depends upon the shape of the given regions and the set of orientations. When the orientations to consider are the ones given by the axes and the regions are axis-parallel rectangles, we obtain a polynomial time approximation scheme.

REFERENCES

• 1: S. Avelar and M. Müller. Generating topologically correct schematic maps. In Proc. 9th Int. Symp. on Spatial Data Handling, pages 4a.28--4a.35, 2000.
• 2: Brenda S. Baker, Approximation algorithms for NP-complete problems on planar graphs, Journal of the ACM (JACM), v.41 n.1, p.153-180, Jan. 1994 [doi>10.1145/174644.174650]
• 3: Thomas Barkowsky , Longin Jan Latecki , Kai-Florian Richter, Schematizing Maps: Simplification of Geographic Shape by Discrete Curve Evolution, Spatial Cognition II, Integrating Abstract Theories, Empirical Studies, Formal Methods, and Practical Applications, p.41-53, January 2000
• 4: Sergio Cabello , Mark de Berg , Steven van Dijk , Marc van Kreveld , Tycho Strijk, Schematization of road networks, Proceedings of the seventeenth annual symposium on Computational geometry, p.33-39, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378609]
• 5: K. Daniels and V. J. Milenkovic. Multiple translational containment, part i: An approximate algorithm. Algorithmica, 19(1--2):148--182, September 1997.
• 6: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 7: G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.
• 8: D. Elroi. Schematic views of networks: Why not have it all. In Proc. of the 1991 GIS for Transportation Symposium, pages 59--76. http://www.elroi.com/fr2_publications.html, 1991.
• 9: Roberto Grossi , Elena Lodi, Simple planar graph partition into three forests, Discrete Applied Mathematics, v.84 n.1-3, p.121-132, May 15, 1998 [doi>10.1016/S0166-218X(98)00007-9]
• 10: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 11: Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985 [doi>10.1145/2455.214106]
• 12: D. Lichtenstein. Planar formulae and their uses. SIAM J. Comput., 11(2):329--343, 1982.
• 13: Gabriele Neyer, Line Simplification with Restricted Orientations, Proceedings of the 6th International Workshop on Algorithms and Data Structures, p.13-24, August 11-14, 1999
• 14: Joseph O'Rourke, Visibility, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 15: Micha Sharir, Algorithmic motion planning, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 16: E. Welzl. Smallest enclosing disks (balls and ellipsoids). In H. Maurer, editor, New Results and New Trends in Computer Science, volume 555 of Lecture Notes Comput. Sci., pages 359--370. Springer-Verlag, 1991.
• 17: A. Wolff and T. Strijk. The Map-Labeling Bibliography. http://www.math-inf.uni-greifswald.de/map-labeling/bibliography/, 1996.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms