de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Connected Area Partitioning

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44616

Hert,  Susan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Hert, S. (2001). Connected Area Partitioning. In Proceedings of the 17th European Workshop on Computational Geometry (CG-01) (pp. 35-38). Berlin, Germany: Freie Universität Berlin.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-3181-A
Zusammenfassung
We present an algorithm to solve the following polygon partitioning problem, which is motivated by a terrain-covering application in robotics: Given a simply connected polygon $\cal P$ and values \subrange{a}{1}{p+1} such that $\sum_{i = 1}^{p+1} a_i = Area({\cal P})$, find a partitioning of $\cal P$ into $p+1$ polygons \subrange{P}{1}{p+1} such that $Area(P_i) = a_i$ for all $i$ and polygon $P_{p+1}$ is connected to each of the other polygons. The algorithm we present runs in $O(n + q \log q + pn)$ time for a polygon with $n$ vertices that has been partitioned into $q$ convex pieces.