Indexing planar point quartets via geometric attributes

ABSTRACT

An index is devised to support position-independent search for images containing quartets of icons. Point quartets exist that do not unambiguously map to quadrilaterals, however, four points do unambiguously determine a set of six interpoint line segments. Values for the "size", "shape", and "orientation" attributes of an icon quartet can be derived as functions of this interpoint line set, and can be used to construct a point-based index, in which each point quartet maps to a single point in the resulting hyperdimensional index space. Orientation can be represented by a single, spatially closed dimension. However, assignment of a reference direction for quartets possessing a k-fold rotational symmetry presents a significant challenge. Methods are described for determining shape and orientation attributes for point quartets, and for mapping these attributes onto a set of attribute axes to form a combined index. The orientation computation supplies, as a byproduct, one component of the shape attribute. All attributes are continuous with respect to small variations in the indexed point quartets.

REFERENCES

• 1: Charles B. Cranston , Hanan Samet, Efficient position-independent iconic search using an R-theta index, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183471.1183478]
• 2: C. B. Cranston and H. Samet. Indexing point triples via triangle geometry. In Proceedings of the 23rd IEEE International Conference on Data Engineering, pages 936--945, Istanbul, Turkey, Apr. 2007.
• 3: E. J. Groth. A pattern-matching algorithm for two-dimensional coordinate lists. The Astronomical Journal, 91(5):1244--1248, May 1986.
• 4: S. Roweis, D. Lang, K. Mierle, D. Hogg, and M. Blanton. Making the Sky Searchable: Fast Geometry Hashing for Automated Astrometry. Available as http://cosmo.nyu.edu/hogg/research/2006/09/28/astrometry_google.pdf on the web.
• 5: Hanan Samet, Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 6: P. B. Stetson. In B. Barbuy, E. Janot-Pacheco, A. M. Magalhães, and S. M. Viegas, editors, V Advanced School of Astrophysics, Image and Data Processing/Interstellar Dust. Instituto Astrônomico e Geofísico, Universidade de São Paulo, Brazil, 1989. An alternative description is at http://nedwww.ipac.caltech.edu/level5/Stetson/Stetson5_2.html.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

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

General Terms:
Algorithms