Title: Approximate Range Searching: From the Absolute Model to Relative Model

Speaker: Guilherme Dias da Fonseca
UFRJ, Rio de Janeiro

Date: Friday  April 24, 2009
Time 11:00-11:50
Venue: Room 3464, HKUST

Abstract: 
Range searching consists of preprocessing a set of points in order to
efficiently compute the number of points inside a query region. In the
approximate version, the query region has a fuzzy boundary and the
points on the fuzzy boundary can be counted as inside or outside the
query region. In the absolute model, the the thickness of the fuzzy
boundary is defined independently of the query region. In the relative
model, the thickness of the fuzzy boundary is proportional to the
diameter of the query region. Historically, the relative model was
studied first. The original data structures for the relative model are
quite complicated because they are based on Approximate Voronoi
Diagrams. On the other hand, the absolute model data structures are
quite simple. In this talk, we show how to obtain simpler and more
efficient data structures for the relative model by using techniques
developed for the absolute model.

Joint work with Sunil Arya and David Mount.