| Presentation | 2010-01-25 Zone Diagrams in Euclidean Spaces and in Other Normed Spaces Akitoshi Kawamura, Takeshi Tokuyama, Jiri Matousek, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Zone diagram is a variation on the classical concept of a Voronoi diagram. Given n sites in a metric space that compete for territory, the zone diagram is an equilibrium state in the competition. Formally it is defined as a fixed point of a certain "dominance" map. Asano, Matousek, and Tokuyama proved the existence and uniqueness of a zone diagram for point sites in Euclidean plane, and Reem and Reich showed existence for two arbitrary sites in an arbitrary metric space. We establish existence and uniqueness for n disjoint compact sites in a Euclidean space of arbitrary (finite) dimension, and more generally, in a finite-dimensional normed space with a smooth and rotund norm. The proof is considerably simpler than that of Asano et al. We also provide an example of non-uniqueness for a norm that is rotund but not smooth. Finally, we prove existence and uniqueness for two point sites in the plane with a smooth (but not necessarily rotund norm. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Tarski fixed point theorem / zone diagrams |
| Paper # | COMP2009-42 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2010/1/18(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Zone Diagrams in Euclidean Spaces and in Other Normed Spaces |
| Sub Title (in English) | |
| Keyword(1) | Tarski fixed point theorem |
| Keyword(2) | zone diagrams |
| 1st Author's Name | Akitoshi Kawamura |
| 1st Author's Affiliation | Department of Computer Science, University of Toronto() |
| 2nd Author's Name | Takeshi Tokuyama |
| 2nd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 3rd Author's Name | Jiri Matousek |
| 3rd Author's Affiliation | Department of Applied Mathematics and Institute of Theoretical Computer Science, Charles University:Institute of Theoretical Computer Science, ETH Zurich |
| Date | 2010-01-25 |
| Paper # | COMP2009-42 |
| Volume (vol) | vol.109 |
| Number (no) | 391 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |