The direct dominance problem

ABSTRACT

Given two points a=(a1,a2,…,ad) and b=(b1,b2,…,bd) in d-dimensional space, a dominates b if a≠b and for each i=1…d holds ai≥bi. The direct dominance problem consists of computing a relation of minimal size on a given set of n points such that the transitive closure of the relation gives all the dominances in the set. We present an &Ogr;(n log n +k) time and &Ogr;(n) space algorithm for the problem of two-dimensional space. The algorithm is optimal within a constant factor. Further, we show that the three-dimensional problem can be solved in &Ogr;((n+k) log2n) time and space, or alternatively in &Ogr;((n+k) log3n) time and &Ogr;((n+k)log n) space.

REFERENCES

• 1: [B] Bentley, J. L., Solutions to Klee's rectangle problems. Dept. of Computer Science, Carnecie-Mellon University, Manuscript, 1977.
• 2: [EM] Edelsbrunner, H., and H. A. Maurer, On the intersection of orthogonal objects. Inf. Proc. Letters 13 (1981), 177-181.
• 3: [EO] Edelsbrunner, H., and M. H. Overmars, On the equivalence of some rectangle problems. Inf. Proc. Letters 14 (1982), 124-127.
• 4: [GW] Güting, R. H., and D. Wood, The parenthesis tree. Inf. Sciences 27 (1982), 151-162.
• 5: [K] Klein, R., Direct dominance of points. Report 154, Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, 1985.
• 6: H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
• 7: [LP] Lee, D. T., and F. P. Preparata, An improved algorithm for the rectangle enclosure problem. J. of Algorithms 3 (1982), 218-224.
• 8: [Lu] Lueker, G., A transformation for adding range restriction capability to dynamic data structures for decomposable searching problems. Report 129, Department of Information and Computer Science, University of California, 1979.
• 9: [McC] McCreight, E. M., Efficient algorithms for enumerating intersecting intervals and rectangles. Report CSL-80-9, Xerox PARC, 1980.
• 10: [NR] Nievergelt, J., and E. M. Reingold, Binary search trees of bounded balance. SIAM J. Comput. 2 (1973), 33-43.
• 11: [VW] Vaishnavi, V., and D. Wood, Data structures for rectangle containment and enclosure problems. Computer Graphics and Image Processing 13 (1980), 372-384.
• 12: [W] Willard, D. E., An introduction to super B-trees. Report 79-01, Department of Computer Science, University of Iowa, 1979.

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Design, Measurement, Performance, Theory