New techniques for computing order statistics in Euclidean space (extended abstract)

ABSTRACT

Given a finite point-set S in E2, how hard is it to compute the &kgr;th largest interdistance, or say, the &kgr;th largest slope or &kgr;th largest triangular area formed by points of S? We examine the complexity of a general class of problems built from these examples, and present a number of techniques for deriving nontrivial upper bounds. Surprisingly, these bounds often match or come very close to the complexity of the corresponding extremal problems (e.g. computing the largest or smallest interdistance, slope, etc.)

REFERENCES

• 1: Jon Louis Bentley , Michael Ian Shamos, Divide-and-conquer in multidimensional space, Proceedings of the eighth annual ACM symposium on Theory of computing, p.220-230, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803652]
• 2: [Bl] Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E. Time bounds for selection, JCSS, 7 (4), pp. 448-461, 1973.
• 3: James E. Boyce , David P. Dobkin , Robert L.(Scot) Drysdale, III , Leo J. Guibas, Finding extremal polygons, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.282-289, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802202]
• 4: [CGL] Chazelle, B., Guibas, L.J., Lee, D.T. The power of geometric duality, Proc. 24th IEEE Annu. Symp. Found. Comput. Sci. (1983), pp. 217-225.
• 5: [CW] Chin, F., Wang, CA. Minimum vertex distance between separable convex polygons, Info. Proc. Lett., 18 (1984), pp. 41-45.
• 6: [C] Cole, R. Searching and storing similar lists, Tech. Rep. No. 88, New York Univ., Oct. 1983.
• 7: [DL] Dobkin, D.P., Lipton, R.J. Multidimensional searching problems, SIAM J. on Comput. 5 (2), pp. 181- 186, 1976.
• 8: [EOS] Edelsbrunner, H., O'Rourke, J., Seidel, R. Constructing arrangements of lines and hyperplanes with applications, Proc. 24th IEEE Annu. Symp. Found. Comput. Sci. (1983), pp. 83-91.
• 9: [FJ1] Frederickson, G.N., Johnson, D.B. The complexity of selection and ranking in X + Y and matrices with sorted columns, JCSS, 24 (1982), pp. 197-208.
• 10: [FJ2] Frederickson, G.N., Johnson, D.B. Finding kth paths and p-centers by generating and searching good data structures, J. of Alg., 4 (1983), pp. 61-80.
• 11: [FJ3] Frederickson, G.N., Johnson, D.B. Generalized selection and ranking: sorted matrices, SIAM J. on Comput., 13 (1), pp. 14-30, 1984.
• 12: Zvi Galil , Nimrod Megiddo, A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort, Journal of the ACM (JACM), v.26 n.1, p.58-64, Jan. 1979 [doi>10.1145/322108.322114]
• 13: [H] Henrici, P. Applied and computational complex analysis , Wiley & sons, New York, 1977.
• 14: [JM] Johnson, D.B., Mizoguchi, T. Selecting the k-th element in X + Y and X1 + X2 + ... + Xm, SIAM J. on Comput., 7, pp. 147-153, 1978.
• 15: [MT] McKenna, M., Toussaint G.T. Finding the minimum vertex distance between two disjoint convex polygons in linear time, Tech. Rep. SOCS-83-6, April 1983.
• 16: [Me] Meggido, N., Tamir, A., Zemel, E., Chandrasekaran, R. An O(n log² n) algorithm for the kth longest path in a tree with applications to location problems, SIAM J. on Comput., 10 (2), pp. 328-337, May 1981.
• 17: [Or] O'Rourke, J., Aggarwal, A., Maddila, S., Baldwin, M. An optimal algorithm for finding minimal enclosing triangles, Tech. Rep. JHU/EECS-84/08, Dept. of EE/CS. Johns Hopkins Univ. (1984).
• 18: 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]
• 19: [S] Shamos, M.I. Geometry and statistics: problems at the interface, Algorithms and complexity: new directions and recent results, ed. J.F. Traub, Academic Press, New York, pp. 251-280, 1976.
• 20: [T] Toussaint, G.T. An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons, Proc. 21st Allerton Conf. on Comm. Control and Comput. (1983), pp. 457-458.
• 21: [Y] Yao, A.C. On constructing minimum spanning tree in k-dimensional space and related problems, SIAM J. on Comput. 11 (4), pp. 721-736, 1982.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional 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

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

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