Capacity-Constrained Voronoi Tessellations : Computation and Applications

Lade...
Vorschaubild
Dateien
Diss_Balzer.pdf
Diss_Balzer.pdfGröße: 34.46 MBDownloads: 445
Datum
2009
Autor:innen
Balzer, Michael
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Kapazitätsbeschränkte Voronoi-Diagramme: Berechnung und Anwendungen
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Dissertation
Publikationsstatus
Published
Erschienen in
Zusammenfassung

Voronoi tessellations specify a partition of a given space according to a set of sites where all points in that space are assigned to the closest site. Capacity-constrained Voronoi tessellations are special cases of Voronoi tessellations in which the region of each site has a predefined area. For example, the capacity constraint could state that each region in a Voronoi tessellation must have the same area, or it could state that all regions have individually defined areas. Thus, the capacity constraint allows us to control the spatial influence of the sites in the tessellation.
Unfortunately, there exists no straightforward approach for computing capacity-constrained Voronoi tessellations. Rather, they have to be generated with iterative optimization techniques. In this thesis, we present three different approaches for the computation of capacity-constrained Voronoi tessellations. The algorithms are tailored for either continuous or discrete spaces, and allow us to employ different distance functions that result in Voronoi tessellations with different characteristics. The presented continuous space algorithms modify the locations and weights of the sites, thereby reducing the error between the current and the desired areas of the regions. Although a proof of convergence is still an open research problem, our experiments showed their reliable convergence towards arbitrarily precise capacity-constrained Voronoi tessellations. In contrast, our discrete space algorithm starts with an arbitrary assignment of the points in the discrete space to the sites that fulfills the capacity constraint. This assignment is then optimized until it achieves an equilibrium state that represents a valid Voronoi tessellation. The convergence of the algorithm to such an equilibrium state is guaranteed.
Based on these three algorithms, we present two applications that utilize capacity-constrained Voronoi tessellations. The first application are \emph{Voronoi treemaps} for the visualization of attributed hierarchies in the domain of information visualization. This application focuses on the resulting polygonal regions of the Voronoi tessellations. The second application are capacity-constrained point distributions as a general purpose method for sampling-related tasks in the domain of computer graphics. This application focuses not on the tessellations itself but on the resulting distributions of sites. Both applications represent significant advances in their field with respect to the flexibility of the method and the quality of their results.

Zusammenfassung in einer weiteren Sprache

Eine Voronoi-Tessellierung beschreibt eine Partition eines gegebenen Raumes entsprechend einer Menge sogenannter Zentren, die alle Punkte des Raumes dem nächstgelegenen Zentrum zuweist. Kapazitätsbeschränkte Voronoi-Tessellierungen sind Spezialfälle von Voronoi-Tessellierungen in denen die Region jedes Zentrums einen vorbestimmten Flächeninhalt besitzt. Solch eine Kapazitätsbeschränkung kann zum Beispiel fordern, dass alle Regionen den gleichen Flächeninhalt haben sollen, oder sie kann fordern, dass jede Region einen individuell definierten Flächeninhalt haben soll. Mit Kapazitätsbeschränkungen wird somit der räumliche Einfluss der einzelnen Zentren in der Partitionierung gesteuert.
Kapazitätsbeschränkte Voronoi-Tessellierungen können leider nicht direkt berechnet werden. Stattdessen erfolgt ihre Berechnung mithilfe von iterativen Optimierungsverfahren. In dieser Arbeit präsentieren wir drei Ansätze für die Berechnung von kapazitätsbeschränkten Voronoi-Tessellierungen. Die entsprechenden Algorithmen sind dabei entweder für kontinuierliche oder für diskrete Räume konzipiert, und erlauben eine flexible Verwendung verschiedener Metriken für die Konstruktion von Voronoi-Tessellierungen mit unterschiedlichen Eigenschaften. Unsere Algorithmen für kontinuierliche Räume verändern die Position oder das Gewicht eines Zentrums, um dadurch schrittweise die Differenzen zwischen den tatsächlichen und den gewünschten Flächeninhalten der Regionen zu verringern. Auch wenn wir keinen Nachweis für die Konvergenz dieser Algorithmen geben können, so haben unsere Experimente trotzdem gezeigt, dass sich damit kapazitätsbeschränkte Voronoi-Tessellierungen verlässlich und beliebig genau berechnen lassen. Im Gegensatz dazu beginnt unser Algorithmus für diskrete Räume mit einer beliebigen Zuordnung von Punkten des diskreten Raumes zu den Zentren, welche zunächst einzig und allein die Kapazitätsbeschränkung erfüllen muss. Diese Zuordnung wird dann schrittweise optimiert bis ein Gleichgewichtszustand erreicht ist, in dem die Zuordnung einer gültigen Voronoi-Tessellierung entspricht. Die Konvergenz des Algorithmus in solch einen Gleichgewichtszustand ist dabei garantiert.
Aufbauend auf diesen Algorithmen präsentieren wir zwei Anwendungen für kapazitätsbeschränkte Voronoi-Tessellierungen. Die erste Anwendung sind Voronoi Treemaps für die Visualisierung von attributierten Hierarchien im Bereich der Informationsvisualisierung. Diese Anwendung konzentriert sich dabei auf die polygonalen Regionen der Voronoi-Tessellierungen. Die zweite Anwendung sind kapazitätsbeschränkte Punktverteilungen als eine universelle Methode für Diskretisierungsverfahren im Bereich der Computergrafik. Diese Anwendung konzentriert sich dabei auf die entstehenden Verteilungen der Zentren. Beide Anwendungen repräsentieren signifikante Fortschritte in ihrem jeweiligen Bereich in Bezug auf die Flexibilität der Methode als solche und in Bezug auf die Qualität der Ergebnisse.

Fachgebiet (DDC)
004 Informatik
Schlagwörter
Voronoi tessellation, capacity constraint, Voronoi treemaps, point distributions
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BALZER, Michael, 2009. Capacity-Constrained Voronoi Tessellations : Computation and Applications [Dissertation]. Konstanz: University of Konstanz
BibTex
@phdthesis{Balzer2009Capac-5842,
  year={2009},
  title={Capacity-Constrained Voronoi Tessellations : Computation and Applications},
  author={Balzer, Michael},
  address={Konstanz},
  school={Universität Konstanz}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/5842">
    <dcterms:abstract xml:lang="eng">Voronoi tessellations specify a partition of a given space according to a set of sites where all points in that space are assigned to the closest site. Capacity-constrained Voronoi tessellations are special cases of Voronoi tessellations in which the region of each site has a predefined area. For example, the capacity constraint could state that each region in a Voronoi tessellation must have the same area, or it could state that all regions have individually defined areas. Thus, the capacity constraint allows us to control the spatial influence of the sites in the tessellation.&lt;br /&gt;Unfortunately, there exists no straightforward approach for computing capacity-constrained Voronoi tessellations. Rather, they have to be generated with iterative optimization techniques. In this thesis, we present three different approaches for the computation of capacity-constrained Voronoi tessellations. The algorithms are tailored for either continuous or discrete spaces, and allow us to employ different distance functions that result in Voronoi tessellations with different characteristics. The presented continuous space algorithms modify the locations and weights of the sites, thereby reducing the error between the current and the desired areas of the regions. Although a proof of convergence is still an open research problem, our experiments showed their reliable convergence towards arbitrarily precise capacity-constrained Voronoi tessellations. In contrast, our discrete space algorithm starts with an arbitrary assignment of the points in the discrete space to the sites that fulfills the capacity constraint. This assignment is then optimized until it achieves an equilibrium state that represents a valid Voronoi tessellation. The convergence of the algorithm to such an equilibrium state is guaranteed.&lt;br /&gt;Based on these three algorithms, we present two applications that utilize capacity-constrained Voronoi tessellations. The first application are \emph{Voronoi treemaps} for the visualization of attributed hierarchies in the domain of information visualization. This application focuses on the resulting polygonal regions of the Voronoi tessellations. The second application are capacity-constrained point distributions as a general purpose method for sampling-related tasks in the domain of computer graphics. This application focuses not on the tessellations itself but on the resulting distributions of sites. Both applications represent significant advances in their field with respect to the flexibility of the method and the quality of their results.</dcterms:abstract>
    <dc:contributor>Balzer, Michael</dc:contributor>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:34Z</dc:date>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5842/1/Diss_Balzer.pdf"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:format>application/pdf</dc:format>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
    <dcterms:alternative>Kapazitätsbeschränkte Voronoi-Diagramme: Berechnung und Anwendungen</dcterms:alternative>
    <dcterms:issued>2009</dcterms:issued>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:34Z</dcterms:available>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5842/1/Diss_Balzer.pdf"/>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <dc:creator>Balzer, Michael</dc:creator>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5842"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:language>eng</dc:language>
    <dcterms:title>Capacity-Constrained Voronoi Tessellations : Computation and Applications</dcterms:title>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
July 9, 2009
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Begutachtet
Diese Publikation teilen