Rectangular Point Location in d Dimensions with Applications

Open Access

1 January 1986

journal article
Published by Oxford University Press (OUP) in The Computer Journal

Vol. 29 (1) , 76-82
https://doi.org/10.1093/comjnl/29.1.76

Abstract

Rectangle location search in d dimensions is finding the d-dimensional axis-parallel box of a non-overlapping collection C that contains a query point. A new data structure is proposed that requires optimal space and 0(log^d|C|) time for a search. The significance of this data structure in practical applications is substantiated by empirical examinations of its behaviour.

Keywords

RECTANGLE LOCATION
LOCATION SEARCH
DATA STRUCTURE
DIMENSIONAL AXIS
OPTIMAL SPACE
QUERY POINT
AXIS PARALLEL
OVERLAPPING COLLECTION

This publication has 0 references indexed in Scilit: