Zone diagrams in Euclidean spaces and in other normed spaces

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F10%3A10046708" target="_blank" >RIV/00216208:11320/10:10046708 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Zone diagrams in Euclidean spaces and in other normed spaces

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Zone diagrams in Euclidean spaces and in other normed spaces

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2010

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 2010 annual symposium on Computational geometry

ISBN

978-1-4503-0016-2

ISSN

—

e-ISSN

—

Počet stran výsledku

6

Strana od-do

—

Název nakladatele

Association for Computing Machinery

Místo vydání

Neuveden

Místo konání akce

Snowbird, Utah

Datum konání akce

13. 6. 2010

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000281594400028