MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Bast, Hannah
Hert, Susan		dblp
dblp
Editor(s):
Bremner, Daviddblp
BibTeX cite key*:
bh-app-00
Title, Booktitle
Title*:
The Area Partitioning Problem
Booktitle*:
Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG-00)
Event, URLs
Conference URL::
http://www.cs.unb.ca/conf/cccg
Downloading URL:
Event Address*:
Fredericton, New Brunswick, Canada
Language:
English
Event Date*
(no longer used):
August 16th - 19th
Organization:
Event Start Date:
21 May 2022
Event End Date:
21 May 2022
Publisher
Name*:
University of New Brunswick
URL:
Address*:
Fredericton, Canada
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
August
Pages:
163-171
Year*:
2000
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
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.
Keywords:
polygon partitioning, robotics, terrain covering, NP-hard
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, university publications list, MPII FTP Server, working group publication list, MPG publications list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{bh-app-00,
AUTHOR = {Bast, Hannah and Hert, Susan},
 EDITOR = {Bremner, David},
 TITLE = {The Area Partitioning Problem},
 BOOKTITLE = {Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG-00)},
 PUBLISHER = {University of New Brunswick},
 YEAR = {2000},
 PAGES = {163--171},
 ADDRESS = {Fredericton, New Brunswick, Canada},
 MONTH = {August},
}

Entry last modified by Susan Hert, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Susan Hert		Created
01/18/2001 07:31:06 PM
Revisions
3.
2.
1.
0.
Editor(s)
Susan Hert
Uwe Brahm
Anja Becker
Susan Hert
Edit Dates
02/08/2001 10:36:55
04/09/2001 12:08:34 PM
14.03.2001 13:15:51
18/01/2001 19:31:06