On Voronoi diagrams in the L p -metric in higher dimensions
| العنوان: | On Voronoi diagrams in the L p -metric in higher dimensions |
|---|---|
| المؤلفون: | Ngoc-Minh Lê |
| المصدر: | Lecture Notes in Computer Science ISBN: 9783540577850 STACS |
| بيانات النشر: | Springer Berlin Heidelberg, 1994. |
| سنة النشر: | 1994 |
| مصطلحات موضوعية: | Combinatorics, Integer, Degree (graph theory), Betti number, Algebraic variety, Power diagram, Algebraic number, Voronoi diagram, General position, Mathematics |
| الوصف: | We prove upper bounds on the number of L p -spheres passing through D+1 points in general position in D-space, and on the sum of the Betti numbers of the intersection of bisectors in the L p -metric, where p is an even positive integer. The bounds found, surprisingly, do not depend on p. The proofs for these bounds involve the techniques of Milnor [14] and Thorn [20] for finding bounds 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, 16]. Furthermore, using the theory of degree of mappings in D-space we prove that for even p the number of L p -spheres passing through D+1 points in general position is odd. Combined with results in [10, 11], our results clarify the structure of Voronoi diagrams based on the L p -metric (with even p) in 3-space. |
| ردمك: | 978-3-540-57785-0 |
| DOI: | 10.1007/3-540-57785-8_184 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::9713dd10a7d7125c5fed2ff0f17bc9f9 https://doi.org/10.1007/3-540-57785-8_184 |
| رقم الانضمام: | edsair.doi...........9713dd10a7d7125c5fed2ff0f17bc9f9 |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9783540577850 |
|---|---|
| DOI: | 10.1007/3-540-57785-8_184 |