skip to main content
10.5555/1283383.1283464acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Zone diagrams: existence, uniqueness and algorithmic challenge

Published: 07 January 2007 Publication History

Abstract

A zone diagram is a new variation of the classical notion of Voronoi diagram. Given points (sites) P1,...,Pn in the plane, each Pi is assigned a region Ri, but in contrast to the ordinary Voronoi diagrams, the union of the Ri has a nonempty complement, the neutral zone. The defining property is that each Ri consists of all x ∈ R2 that lie closer (non-strictly) to Pi. than to the union of all the other Rj, ji. Thus, the zone diagram is defined implicitly, by a "fixed-point property," and neither its existence nor its uniqueness seem obvious. We establish existence using a general fixed-point result (a consequence of Schauder's theorem or Kakutani's theorem); this proof should generalize easily to related settings, say higher dimensions. Then we prove uniqueness of the zone diagram, as well as convergence of a natural iterative algorithm for computing it, by a geometric argument, which also relies on a result for the case of two sites in an earlier paper. Many challenging questions remain open.

References

[1]
T. Asano, J. Matoušek, T. Tokuyama. The distance tri-sector curve, Proceedings of the 38th ACM Symposium on Theory of Computing (2006), pp. 336--343.
[2]
T. Asano and T. Tokuyama. Drawing Equally-Spaced Curves between Two Points, Proc. Fall Conference on Computational Geometry, Boston, Massachusetts, November 2004, pp. 24--25.
[3]
F. Aurenhammer. Voronoi Diagrams --- A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys 23--3 (1991) pp. 345--405.
[4]
D. W. Curtis and R. M. Schori. Hyperspaces of Peano continua are Hilbert cubes. Fundam. Math. 101 (1978), pp. 19--38.
[5]
A. Okabe, B. Boots, K. Sugihara. Spatial Tessellations, Concepts and Applications of Voronoi Diagrams, John Wiley & Sons, New York, NY 1992.
[6]
E. Zeidler, Nonlinear functional analysis and its applications. Volume I: Fixed-point theorems, 2nd corr. printing, Springer, New York, 1993.
  1. Zone diagrams: existence, uniqueness and algorithmic challenge

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
    January 2007
    1322 pages
    ISBN:9780898716245
    • Conference Chair:
    • Harold Gabow

    Sponsors

    Publisher

    Society for Industrial and Applied Mathematics

    United States

    Publication History

    Published: 07 January 2007

    Check for updates

    Qualifiers

    • Article

    Acceptance Rates

    SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;
    Overall Acceptance Rate 411 of 1,322 submissions, 31%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 218
      Total Downloads
    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 18 Feb 2025

    Other Metrics

    Citations

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media