Indexing planar point quartets via geometric attributes

TitleIndexing planar point quartets via geometric attributes
Publication TypeConference Papers
Year of Publication2008
AuthorsCranston CB, Samet H
Conference NameProceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems
Date Published2008///
Conference LocationNew York, NY, USA
ISBN Number978-1-60558-323-5

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.