Constructing the Voronoi diagram of a set of line segments in parallel

Michael T. Goodrich; Colm Ó'Dúnlaing; Chee K. Yap

doi:10.1007/BF01188708

Constructing the Voronoi diagram of a set of line segments in parallel

Michael T. Goodrich, Colm Ó'Dúnlaing, Chee K. Yap

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper we give a parallel algorithm for constructing the Voronoi diagram of a polygonal scene, i.e., a set of line segments in the plane such that no two segments intersect except possibly at their endpoints. Our algorithm runs in O(log²n) time using O(n) processors in the CREW PRAM model.

Original language	English (US)
Pages (from-to)	128-141
Number of pages	14
Journal	Algorithmica
Volume	9
Issue number	2
DOIs	https://doi.org/10.1007/BF01188708
State	Published - Feb 1993

Keywords

PRAM
Parallel algorithm
Voronoi diagram

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/BF01188708

Cite this

@article{4ffc2db1e10d44ee8177b0654dfb5fda,

title = "Constructing the Voronoi diagram of a set of line segments in parallel",

abstract = "In this paper we give a parallel algorithm for constructing the Voronoi diagram of a polygonal scene, i.e., a set of line segments in the plane such that no two segments intersect except possibly at their endpoints. Our algorithm runs in O(log2n) time using O(n) processors in the CREW PRAM model.",

keywords = "PRAM, Parallel algorithm, Voronoi diagram",

author = "Goodrich, {Michael T.} and Colm {\'O}'D{\'u}nlaing and Yap, {Chee K.}",

year = "1993",

month = feb,

doi = "10.1007/BF01188708",

language = "English (US)",

volume = "9",

pages = "128--141",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Constructing the Voronoi diagram of a set of line segments in parallel

AU - Goodrich, Michael T.

AU - Ó'Dúnlaing, Colm

AU - Yap, Chee K.

PY - 1993/2

Y1 - 1993/2

N2 - In this paper we give a parallel algorithm for constructing the Voronoi diagram of a polygonal scene, i.e., a set of line segments in the plane such that no two segments intersect except possibly at their endpoints. Our algorithm runs in O(log2n) time using O(n) processors in the CREW PRAM model.

AB - In this paper we give a parallel algorithm for constructing the Voronoi diagram of a polygonal scene, i.e., a set of line segments in the plane such that no two segments intersect except possibly at their endpoints. Our algorithm runs in O(log2n) time using O(n) processors in the CREW PRAM model.

KW - PRAM

KW - Parallel algorithm

KW - Voronoi diagram

UR - http://www.scopus.com/inward/record.url?scp=0027541360&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027541360&partnerID=8YFLogxK

U2 - 10.1007/BF01188708

DO - 10.1007/BF01188708

M3 - Article

AN - SCOPUS:0027541360

SN - 0178-4617

VL - 9

SP - 128

EP - 141

JO - Algorithmica

JF - Algorithmica

IS - 2

ER -

Constructing the Voronoi diagram of a set of line segments in parallel

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this