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

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

The Area Partitioning Problem

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

Bast,  Hannah
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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

Bast, H., & Hert, S. (2000). The Area Partitioning Problem. In D. Bremner (Ed.), Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG-00) (pp. 163-171). Fredericton, Canada: University of New Brunswick.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-3405-A
Zusammenfassung
Given an arbitrary polygon with $n$ vertices, we wish to partition it into $p$ connected pieces of given areas. The problem is motivated by a robotics application in which the polygon is a workspace that is to be divided among $p$ robots performing a terrain-covering task. We show that finding an area partitioning with minimal cut length is NP-hard in the number of pieces and that it is even hard to approximate to within any factor that is independent of the shape of the polygon. We then present a simple $O(pn)$-time algorithm that produces non-optimal, but often quite reasonable, area partitionings for arbitrary polygons.