Linear data structures for two types of range search

ABSTRACT

We present two algorithms for pictures of polyhedral scenes. These algorithms have been conjectured (and used for some time), but only now been verified. The combinatorial algorithm, proposed by Sugihara, uses counts on the incidence structure to characterize pictures which are generically the projection of sharp polyhedral scenes of planes and points. The geometric algorithm, described by Clerk Maxwell and rediscovered in the last decade, uses a reciprocal diagram in the plane to characterize pictures of strict oriented polyhedra in space.

REFERENCES

• B: Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
• C: Chaselle, B. Filtering search: a new approach to query-an, wering, Proc. 24th Annu. IEEE Symp. Found. Comput. Sci. (1983), 122-132. To appear in SIAM .l. on Comput.
• C1: Chaselle, B. A functional approach to data structures and its use in multidimensional searching, Brown Univ. TR, No. CS-85-16, Sept. 1985. Preliminary version in Proc. 26th FOGS, 1985.
• CE: Chazelle, B., Edelsbrunner, H. Optimal $olutior~s for a Class of Point Retrieval Problems, Tech. Rep. No. CS-84-16, Brown Univ., Providence, 1984.
• CG: Bernard Chazelle , Leonidas J. Guibas, Fractional Cascading: A Data Structuring Technique with Geometric Applications, Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.90-100, July 15-19, 1985
• CGL: Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
• DE: Dobkin, D.P., Edelsbrunner, H. Sp4ce searching for intersecting objects Proc. 25th Annu. IEEE Syrup. Found. Comp. Sci. (1984), 387-392.
• EGS: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• EW: Edelsbrunner, H., Welzl, E. Halfplanar range search in lir~ear space and O(n~'~9~) querl~ time, Rep. Fill, Inst. Inform. Proc., Tech. Univ. Graz, Austria, 1983.
• GBT: Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
• GS: Leo J. Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.221-234, December 1983 [doi>10.1145/800061.808751]
• K: Kirkpatrick, D.G. Optimal search in planar subdivisions, SIAM J. on Comput., Vol. 12, No. 1, pp. 28-35, 1983.
• KLP: 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]
• LT: Lipton, R.J., Tarjan, R.E. Applications of a planar separator theorem, SIAM J. on Comput., Vol. 9, No. 3, pp. 615-627, Aug. 1980.
• M: McCreight, E.M. Priority search trees, Rep. CSL-81-5, Xerox PARC, Palo Alto, 1981.
• MP: Muller, D.E., Preparata, F.P. Finding the ir~tersection of two convex polyhedra, Theoret. Comput. Sci., 7 (1978), 217-236.
• NS: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• W: Will~d, D.E. Polygon retrieval, SIAM J. Comp., 11 (1982), 149-165.
• Y: F. Frances Yao, A 3-space partition and its applications, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.258-263, December 1983 [doi>10.1145/800061.808755]

INDEX TERMS

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

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies
  I.3 COMPUTER GRAPHICS
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Range data

General Terms:
Algorithms, Theory, Verification