Deakin University
Browse

File(s) under permanent embargo

Fitting Voronoi diagrams to planar tesselations

conference contribution
posted on 2013-01-01, 00:00 authored by G Aloupis, H Pérez-Rosés, Guillermo Pineda VillavicencioGuillermo Pineda Villavicencio, P Taslakian, D Trinchet-Almaguer
Given a tesselation of the plane, defined by a planar straight-line graph G, we want to find a minimal set S of points in the plane, such that the Voronoi diagram associated with S 'fits' G. This is the Generalized Inverse Voronoi Problem (GIVP), defined in [12] and rediscovered recently in [3]. Here we give an algorithm that solves this problem with a number of points that is linear in the size of G, assuming that the smallest angle in G is constant.

History

Volume

8288

Pagination

349-361

Location

Rouen, France

Start date

2013-07-10

End date

2013-07-12

ISSN

0302-9743

eISSN

1611-3349

ISBN-13

9783642452772

Language

eng

Publication classification

E1.1 Full written paper - refereed

Copyright notice

2013, Springer-Verlag Berlin Heidelberg

Editor/Contributor(s)

Lecroq T, Mouchard L

Title of proceedings

IWOCA 2013 : Proceedings of the 24th International Workshop on Combinatorial Algorithms 2013

Event

Combinatorial Algorithms. Workshop (24th : 2013 : Rouen, France)

Publisher

Springer

Place of publication

Berlin, Germany

Series

Combinatorial Algorithms Workshop

Usage metrics

    Research Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC