Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

I/O-Efficient Batched Range Counting and Its Applications to Proximity Problems

Tamás LukovszkiContact Information, Anil MaheshwariContact Information and Norbert ZehContact Information

(6)  Heinz-Nixdorf-Institut, Universität Paderborn, Germany
(7)  School of Computer Science, Carleton University, Ottawa, Canada
Abstract
We present an algorithm to answer a set Q of range counting queries over a point set P in d dimensions. The algorithm takes $$
O\left( {sort(\left| P \right| + \left| Q \right|) + \tfrac{{(\left| P \right| + \left| Q \right|)\alpha (\left| P \right|)}}
{{DB}}\log _{M/B}^{d - 1} \tfrac{{\left| P \right| + \left| Q \right|}}
{B}} \right)^1 
$$ I/Os and uses linear space. For an important special case, the α(∣P∣) term in the I/Ocomplexity of the algorithm can be eliminated. We apply this algorithm to constructing t-spanners for point sets in ℝd and polygonal obstacles in the plane, and finding the K closest pairs of a point set in ℝd.
Research supported by NSERC, NCE GEOIDE, and DFG-SFB376.
sort(N) denotes the I/O-complexity of sorting N data items in external memory. See Model of Computation.

Contact Information Tamás Lukovszki
Email: tamas@hni.uni-paderborn.de

Contact Information Anil Maheshwari
Email: maheshwa@scs.carleton.ca

Contact Information Norbert Zeh
Email: nzeh@scs.carleton.ca
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.105 • Server: mpweb16
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)