Sweeping the Sphere

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)

Abstract

We introduce the first sweep line algorithm for computing spherical Voronoi diagrams, which proves that Fortune's method can be extended to points on a sphere surface. This algorithm is similar to Fortune's plane sweep algorithm, sweeping the sphere with a circular line instead of a straight one.
Like its planar counterpart, the novel linear-space algorithm has worst-case optimal running time. Furthermore, it copes very well with degeneracies and is easy to implement. Experimental results show that the performance of our algorithm is very similar to that of Fortune's algorithm, both with synthetic data sets and with real data.
The usual solutions make use of the connection between convex hulls and spherical Delaunay triangulations. An experimental comparison revealed that our algorithm outperforms the freely available implementations that compute convex hulls of point sets in 3D, enabling it to be the preferred choice for computing Voronoi diagrams on the sphere.
Original languageUnknown
Title of host publicationISVD
PublisherIEEE
Pages151-160
ISBN (Print)978-1-4244-7606-0
DOIs
Publication statusPublished - 1 Jan 2010
EventInternational Symposium on Voronoi Diagrams in Science and Engineering (ISVD) -
Duration: 1 Jan 2010 → …

Conference

ConferenceInternational Symposium on Voronoi Diagrams in Science and Engineering (ISVD)
Period1/01/10 → …

Cite this