ORTHANT NEIGHBORHOOD GRAPHS - A Decentralized Approach for Proximity Queries in Dynamic Point Sets

Tobias Germer, Thomas Strothotte

2007

Abstract

This work presents a novel approach for proximity queries in dynamic point sets, a common problem in computer graphics. We introduce the notion of Orthant Neighborhood Graphs, yielding a simple, decentralized spatial data structure based on weak spanners. We present efficient algorithms for dynamic insertions, deletions and movements of points, as well as range searching and other proximity queries. All our algorithms work in the local neighborhood of given points and are therefore independent of the global point set. This makes ONGs scalable to large point sets, where the total number of points does not influence local operations.

Paper Citation

in Harvard Style

Germer T. and Strothotte T. (2007). ORTHANT NEIGHBORHOOD GRAPHS - A Decentralized Approach for Proximity Queries in Dynamic Point Sets . In Proceedings of the Second International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, ISBN 978-972-8865-71-9, pages 85-93. DOI: 10.5220/0002082800850093

in Bibtex Style

@conference{grapp07,
author={Tobias Germer and Thomas Strothotte},
title={ORTHANT NEIGHBORHOOD GRAPHS - A Decentralized Approach for Proximity Queries in Dynamic Point Sets},
booktitle={Proceedings of the Second International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP,},
year={2007},
pages={85-93},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002082800850093},
isbn={978-972-8865-71-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Second International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP,
TI - ORTHANT NEIGHBORHOOD GRAPHS - A Decentralized Approach for Proximity Queries in Dynamic Point Sets
SN - 978-972-8865-71-9
AU - Germer T.
AU - Strothotte T.
PY - 2007
SP - 85
EP - 93
DO - 10.5220/0002082800850093