Sweeping the Sphere

Margarida Paula Neves Mamede

doi:10.1109/ISVD.2010.32

Sweeping the Sphere

Margarida Paula Neves Mamede

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 language	Unknown
Title of host publication	ISVD
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	151-160
ISBN (Print)	978-1-4244-7606-0
DOIs	https://doi.org/10.1109/ISVD.2010.32
Publication status	Published - 1 Jan 2010
Event	International Symposium on Voronoi Diagrams in Science and Engineering (ISVD) - Duration: 1 Jan 2010 → …

Conference

Conference	International Symposium on Voronoi Diagrams in Science and Engineering (ISVD)
Period	1/01/10 → …

Access to Document

10.1109/ISVD.2010.32

Cite this

@inproceedings{369208307bf94147a04827c21011a624,

title = "Sweeping the Sphere",

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.",

keywords = "Sweep algorithms., Spherical Voronoi diagrams",

author = "Mamede, {Margarida Paula Neves}",

year = "2010",

month = jan,

day = "1",

doi = "10.1109/ISVD.2010.32",

language = "Unknown",

isbn = "978-1-4244-7606-0",

pages = "151--160",

booktitle = "ISVD",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

note = "International Symposium on Voronoi Diagrams in Science and Engineering (ISVD) ; Conference date: 01-01-2010",

}

TY - GEN

T1 - Sweeping the Sphere

AU - Mamede, Margarida Paula Neves

PY - 2010/1/1

Y1 - 2010/1/1

N2 - 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.

AB - 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.

KW - Sweep algorithms.

KW - Spherical Voronoi diagrams

U2 - 10.1109/ISVD.2010.32

DO - 10.1109/ISVD.2010.32

M3 - Conference contribution

SN - 978-1-4244-7606-0

SP - 151

EP - 160

BT - ISVD

PB - Institute of Electrical and Electronics Engineers (IEEE)

T2 - International Symposium on Voronoi Diagrams in Science and Engineering (ISVD)

Y2 - 1 January 2010

ER -