A lower bound on Voronoi diagram complexity

Boris Aronov

doi:10.1016/S0020-0190(01)00336-2

A lower bound on Voronoi diagram complexity

Boris Aronov

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

Abstract

A lower bound on Voronoi diagram complexity is presented. The Voronoi diagram is a classification of points of the ambient space according to the identity of the closest site or sites. Results provided evidence that the bound derived from envelope analysis is closer to the truth as the conjecture of Sharir does not hold.

Original language	English (US)
Pages (from-to)	183-185
Number of pages	3
Journal	Information Processing Letters
Volume	83
Issue number	4
DOIs	https://doi.org/10.1016/S0020-0190(01)00336-2
State	Published - Aug 31 2002

Keywords

Computational complexity
Computational geometry
Voronoi diagram

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/S0020-0190(01)00336-2

Cite this

@article{6382d58ceab7491593b556de08084f60,

title = "A lower bound on Voronoi diagram complexity",

abstract = "A lower bound on Voronoi diagram complexity is presented. The Voronoi diagram is a classification of points of the ambient space according to the identity of the closest site or sites. Results provided evidence that the bound derived from envelope analysis is closer to the truth as the conjecture of Sharir does not hold.",

keywords = "Computational complexity, Computational geometry, Voronoi diagram",

author = "Boris Aronov",

note = "Funding Information: 1 B.A. was supported in part by NSF Grants CCR-92-11541, CCR-99-72568, and ITR-00-81964. The work described in this note was carried out during Dagstuhl-Seminar 95-11 on Computational Geometry at the Internationales Begegnungs-und Forschungszen-trum f{\"u}r Informatik (IBFI), Schlo{\ss} Dagstuhl, Germany. This note was finally written while visiting Max-Planck-Institut f{\"u}r Infor-matik, Saarbr{\"u}cken, Germany in the summer of 1997, and finally revised into presentable form in the spring of 2001.",

year = "2002",

month = aug,

day = "31",

doi = "10.1016/S0020-0190(01)00336-2",

language = "English (US)",

volume = "83",

pages = "183--185",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - A lower bound on Voronoi diagram complexity

AU - Aronov, Boris

N1 - Funding Information: 1 B.A. was supported in part by NSF Grants CCR-92-11541, CCR-99-72568, and ITR-00-81964. The work described in this note was carried out during Dagstuhl-Seminar 95-11 on Computational Geometry at the Internationales Begegnungs-und Forschungszen-trum für Informatik (IBFI), Schloß Dagstuhl, Germany. This note was finally written while visiting Max-Planck-Institut für Infor-matik, Saarbrücken, Germany in the summer of 1997, and finally revised into presentable form in the spring of 2001.

PY - 2002/8/31

Y1 - 2002/8/31

N2 - A lower bound on Voronoi diagram complexity is presented. The Voronoi diagram is a classification of points of the ambient space according to the identity of the closest site or sites. Results provided evidence that the bound derived from envelope analysis is closer to the truth as the conjecture of Sharir does not hold.

AB - A lower bound on Voronoi diagram complexity is presented. The Voronoi diagram is a classification of points of the ambient space according to the identity of the closest site or sites. Results provided evidence that the bound derived from envelope analysis is closer to the truth as the conjecture of Sharir does not hold.

KW - Computational complexity

KW - Computational geometry

KW - Voronoi diagram

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

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

U2 - 10.1016/S0020-0190(01)00336-2

DO - 10.1016/S0020-0190(01)00336-2

M3 - Article

AN - SCOPUS:0037206191

SN - 0020-0190

VL - 83

SP - 183

EP - 185

JO - Information Processing Letters

JF - Information Processing Letters

IS - 4

ER -

A lower bound on Voronoi diagram complexity

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this