Home // ADVCOMP 2011, The Fifth International Conference on Advanced Engineering Computing and Applications in Sciences // View article

Advanced Space Filtering for the Construction of 3D Additively Weighted Voronoi Diagram

Authors:
Michal Zemek
Martin Maňák
Ivana Kolingerová

Keywords: computational geometry, additively weighted Voronoi diagram, geometric filter

Abstract:
Spatial relationships among 3D spheres can be described by an additively weighted Voronoi diagram and this diagram can be used for advanced spatial analysis. The diagram can be constructed by an edge tracing algorithm. The problem is that tracing an edge is a time consuming operation, where many spheres are tested. Former approaches make it faster by using space filters and searching for spheres intersecting the filter. But they are inefficient when the spheres have very different radii. Our approach presented in this paper is designed to be fast even on this kind of data. It is based on modified space filters and the search for spheres intersecting the filter is performed in a power diagram.

Pages: 37 to 43

Copyright: Copyright (c) IARIA, 2011

Publication date: November 20, 2011

Published in: conference

ISSN: 2308-4499

ISBN: 978-1-61208-172-4

Location: Lisbon, Portugal

Dates: from November 20, 2011 to November 25, 2011