NDLI: Maintaining Voronoi diagrams in parallel

Content Provider	IEEE Xplore Digital Library
Author	Roos, T.
Copyright Year	1994
Description	Author affiliation: Dept. of Comput. Sci., Federal Inst. of Technol., Zurich, Switzerland (Roos, T.)
Abstract	We are given a set of n points moving continuously along given trajectories in d-dimensional Euclidean space. At each instant, these sites define a Voronoi diagram which changes continuously over time except of certain critical instances, so-called topological events. We present an algorithm for maintaining the Voronoi diagram in parallel over time using only O(1) time per event on a CREW PRAM with O/spl lsqb/n/sup d/2spl rsqb/ processors which is worst-case optimal. This work generalizes the most recent single processor algorithms to PRAMs. Additionally, the presented technique provides the first efficient algorithm for computing static higher dimensional Voronoi diagrams in parallel. Finally, we present a new upper bound on the number of topological events which may appear during the flow of the sites. This result tightens a long-open gap between the upper and lower worst-case bounds, actually providing matching bounds in some cases, and is interesting in its own right.
Starting Page	179
Ending Page	186
File Size	622591
Page Count	8
File Format	PDF
ISBN	0818650907
DOI	10.1109/HICSS.1994.323267
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1994-01-04
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computational geometry Topology Parallel algorithms Complexity theory
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Generalization of Voronoi Diagrams in the Plane

Constructing Levels in Arrangements and Higher Order Voronoi Diagrams

3-Dimensional Euclidean Voronoi Diagrams of Lines with a Fixed Number of Orientations

A Sweepline Algorithm for Higher Order Voronoi Diagrams

Towards dynamic randomized algorithms in computational geometry

Voronoi Diagrams in CGAL, the Computational Geometry Algorithms Library

Approximating Minimization Diagrams and Generalized Proximity Search

Approximating Minimization Diagrams and Generalized Proximity Search

On the combinatorial complexity of euclidean Voronoi cells and convex hulls of d-dimensional spheres

Maintaining Voronoi diagrams in parallel

Similar Documents

Generalization of Voronoi Diagrams in the Plane

Constructing Levels in Arrangements and Higher Order Voronoi Diagrams

3-Dimensional Euclidean Voronoi Diagrams of Lines with a Fixed Number of Orientations

A Sweepline Algorithm for Higher Order Voronoi Diagrams

Towards dynamic randomized algorithms in computational geometry

Voronoi Diagrams in CGAL, the Computational Geometry Algorithms Library

Approximating Minimization Diagrams and Generalized Proximity Search

Approximating Minimization Diagrams and Generalized Proximity Search

On the combinatorial complexity of euclidean Voronoi cells and convex hulls of d-dimensional spheres

Maintaining Voronoi diagrams in parallel