# The effect of corners on the complexity of approximate range searching

Title | The effect of corners on the complexity of approximate range searching |

Publication Type | Journal Articles |

Year of Publication | 2009 |

Authors | Arya S, Malamatos T, Mount D |

Journal | Discrete & Computational Geometry |

Volume | 41 |

Issue | 3 |

Pagination | 398 - 443 |

Date Published | 2009/// |

Abstract | Given an n-element point set in ℝ d , the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup sum, of the points lying within a given query range η can be determined quickly. In ε-approximate range searching we assume that η is bounded, and the sum is required to include all the points that lie within η and may additionally include any of the points lying within distance ε⋅diam(η) of η’s boundary.In this paper we contrast the complexity of approximate range searching based on properties of the semigroup and range space. A semigroup (S,+) is idempotent if x+x=x for all x∈S, and it is integral if for all k≥2, the k-fold sum x+⋅⋅⋅+x is not equal to x. Recent research has shown that the computational complexity of approximate spherical range searching is significantly lower for idempotent semigroups than it is for integral semigroups in terms of the dependencies on ε. In this paper we consider whether these results can be generalized to other sorts of ranges. We show that, as with integrality, allowing sharp corners on ranges has an adverse effect on the complexity of the problem. In particular, we establish lower bounds on the worst-case complexity of approximate range searching in the semigroup arithmetic model for ranges consisting of d-dimensional unit hypercubes under rigid motions. We show that for arbitrary (including idempotent) semigroups and linear space, the query time is at least \varOmega(1/{\varepsilon }^{d-2\sqrt{d}}) . In the case of integral semigroups we prove a tighter lower bound of Ω(1/ε d−2). These lower bounds nearly match existing upper bounds for arbitrary semigroups. |

DOI | 10.1007/s00454-009-9140-z |