article

Free access

On the Peeper's Voronoi diagram

Authors:

F. Aurenhammer,

G. StöcklAuthors Info & Claims

ACM SIGACT News, Volume 22, Issue 4

Pages 50 - 59

https://doi.org/10.1145/126546.126548

Published: 01 September 1991 Publication History

PDF eReader

Abstract

In the peeper's Voronoi diagram for n sites, any point in the plane belongs to the region of the closest site visible from it. Visibility is constrained to a segment on a line avoiding the convex hull of the sites. We show that the peeper's Voronoi diagram attains a size of Θ(n²) in the worst case, and that it can be computed in O(n²)time and space.

Cited By

View all

Fan CLuo JWang WZhu B(2014)Voronoi diagram with visual restrictionTheoretical Computer Science10.1016/j.tcs.2013.08.008532(31-39)Online publication date: May-2014
https://doi.org/10.1016/j.tcs.2013.08.008
Aurenhammer FSu BXu YZhu B(2014)A note on visibility-constrained Voronoi diagramsDiscrete Applied Mathematics10.1016/j.dam.2014.04.009174(52-56)Online publication date: Sep-2014
https://doi.org/10.1016/j.dam.2014.04.009
Basu Roy SDas GDas S(2012)Algorithms for computing Best Coverage Path in the presence of obstacles in a sensor fieldJournal of Discrete Algorithms10.1016/j.jda.2012.01.00413(86-97)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1016/j.jda.2012.01.004
Show More Cited By

Index Terms

On the Peeper's Voronoi diagram
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Half-Plane Voronoi Diagram
ISVD '11: Proceedings of the 2011 Eighth International Symposium on Voronoi Diagrams in Science and Engineering

In normal Voronoi diagram, each site is able to see all points in the plane. In this paper, we study the problem such that each site is only able to see half-plane and construct the so-called Half-plane Voronoi Diagram (HPVD). We show that the half-...
Uncertain Voronoi diagram

In this paper, we introduce the fuzzy Voronoi diagram as an extension of the Voronoi diagram. We assume Voronoi sites to be fuzzy points and then define the Voronoi diagram for this kind of sites, then we provide an algorithm for computing this diagram ...
Efficient computation of 3d clipped voronoi diagram
GMP'10: Proceedings of the 6th international conference on Advances in Geometric Modeling and Processing

The Voronoi diagram is a fundamental geometry structure widely used in various fields, especially in computer graphics and geometry computing. For a set of points in a compact 3D domain (i.e. a finite 3D volume), some Voronoi cells of their Voronoi ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGACT News Volume 22, Issue 4

Fall 1991

16 pages

ISSN:0163-5700

DOI:10.1145/126546

Editor:
Ian Parberry
Univ. of North Texas, Denton

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1991

Published in SIGACT Volume 22, Issue 4

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
239
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)6

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Fan CLuo JWang WZhu B(2014)Voronoi diagram with visual restrictionTheoretical Computer Science10.1016/j.tcs.2013.08.008532(31-39)Online publication date: May-2014
https://doi.org/10.1016/j.tcs.2013.08.008
Aurenhammer FSu BXu YZhu B(2014)A note on visibility-constrained Voronoi diagramsDiscrete Applied Mathematics10.1016/j.dam.2014.04.009174(52-56)Online publication date: Sep-2014
https://doi.org/10.1016/j.dam.2014.04.009
Basu Roy SDas GDas S(2012)Algorithms for computing Best Coverage Path in the presence of obstacles in a sensor fieldJournal of Discrete Algorithms10.1016/j.jda.2012.01.00413(86-97)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1016/j.jda.2012.01.004
Fan CLuo JWang WZhu B(2012)Voronoi diagram with visual restrictionProceedings of the 6th international Frontiers in Algorithmics, and Proceedings of the 8th international conference on Algorithmic Aspects in Information and Management10.1007/978-3-642-29700-7_4(36-46)Online publication date: 14-May-2012
https://dl.acm.org/doi/10.1007/978-3-642-29700-7_4
Roy SDas GDas S(2007)Computing best coverage path in the presence of obstacles in a sensor fieldProceedings of the 10th international conference on Algorithms and Data Structures10.5555/2394893.2394962(577-588)Online publication date: 15-Aug-2007
https://dl.acm.org/doi/10.5555/2394893.2394962
Roy SDas GDas S(2007)Computing Best Coverage Path in the Presence of Obstacles in a Sensor FieldAlgorithms and Data Structures10.1007/978-3-540-73951-7_50(577-588)Online publication date: 2007
https://doi.org/10.1007/978-3-540-73951-7_50
Wang CTsin Y(1998)Finding constrained and weighted Voronoi diagrams in the planeComputational Geometry: Theory and Applications10.1016/S0925-7721(97)00028-X10:2(89-104)Online publication date: 1-May-1998
https://dl.acm.org/doi/10.1016/S0925-7721%2897%2900028-X

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Half-Plane Voronoi Diagram

Uncertain Voronoi diagram

Efficient computation of 3d clipped voronoi diagram

Comments

Information

Published In

Publisher

Publication History

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations