On voronoi diagrams in theL p-metric in ℝD
| العنوان: | On voronoi diagrams in theL p-metric in ℝD |
|---|---|
| المؤلفون: | Ngoc-Minh Lê |
| المصدر: | Discrete & Computational Geometry. 16:177-196 |
| بيانات النشر: | Springer Science and Business Media LLC, 1996. |
| سنة النشر: | 1996 |
| مصطلحات موضوعية: | Discrete mathematics, Degree (graph theory), Betti number, Algebraic variety, Upper and lower bounds, Theoretical Computer Science, Combinatorics, Computational Theory and Mathematics, Integer, Bounded function, Discrete Mathematics and Combinatorics, Geometry and Topology, Voronoi diagram, General position, Mathematics |
| الوصف: | We prove upper bounds on the number ofLp-spheres passing throughD+1 points in general position in ź", and on the sum of the Betti numbers of the intersection of bisectors in theLp-metric, wherep is an even positive integer. The bounds found do not depend onp. Our result implies that the complexity of Voronoi diagrams (for point sites in general position) in theLp-metric is bounded for increasingp. The proof for this upper bound involves the techniques of Milnor [12] and Thom [16] for finding a bound on the sum of the Betti numbers of algebraic varieties, but instead of the usual degree of polynomials we use their additive complexity, and apply results of Benedetti and Risler [2], [13]. Furthermore, we prove that inD dimensions and for evenp the number ofLp-spheres passing throughD+1 points in general position is odd. In particular, combined with results of [8], [9], our results clarify the structure of Voronoi diagrams based on theLp-metric (with evenp) in three dimensions. For the proof we use the theory of degree of continuous mappings in źD, which is a tool widely applied in nonlinear analysis [14]. |
| تدمد: | 1432-0444 0179-5376 |
| DOI: | 10.1007/bf02716806 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::24d826bf6826e7b624fb9b8c45b8702f https://doi.org/10.1007/bf02716806 |
| Rights: | OPEN |
| رقم الانضمام: | edsair.doi...........24d826bf6826e7b624fb9b8c45b8702f |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 14320444 01795376 |
|---|---|
| DOI: | 10.1007/bf02716806 |