Finding tailored partitions

ABSTRACT

We consider the following problem: given a planar set of points S, a measure &mgr; acting on S, and a pair of values &mgr;1 and &mgr;2, does there exist a bipartition S = S1 U S2 satisfying &mgr;(Si) ≤ &mgr;i for i = 1,2? We present algorithms of complexity &Ogr;(n log n) for several natural measures, including the diameter (set measure), the area, perimeter or diagonal of the smallest enclosing axes-parallel rectangle (rectangular measure), and the side length of the smallest enclosing axes-parallel square (square measure). The problem of partitioning S into k subsets, where k ≥ 3, is known to be NP-complete for many of these measures.

REFERENCES

• 1: T. Asano , B. Bhattacharya , M. Keil , F. Yao, Clustering algorithms based on minimum and maximum spanning trees, Proceedings of the fourth annual symposium on Computational geometry, p.252-257, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73419]
• 2: D. Avis. Diameter partitioning. Discrete and Computational Geometry, 1(3):265-276, 1986.
• 3: B. Chazelle. On the convex layers of a planar set. IEEE Twmsactions on Information Theory, IT-31(4):509- 517, July 1985.
• 4: D. S. Johnson. The NP-completeness column. Journal of Algorithms, 3( 1):182-195, 1982.
• 5: N. Meggido and K. Supowit. On the complexity of some common geometric location problems. SIAM Journal of Computing, 13(1):182-196, 1984.
• 6: C. Monma and S. Suri. Partitioning points and graphs to minimize the maximum or the sum of diameters. In Proceedings of the Sixth International Conference on the Theory and Applications of Graphs, John Wiley & Sons, 1988.
• 7: M. Overmars and II. van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23:166-204, 1981.
• 8: F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
• 9: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 10: I. M. Yaglom and V. G. Boltyanskii. Conuez Figures. Holt, Rinehart and Winston, New York, 1961.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Measurement, Theory