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 -