Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update
Options:








Author, Editor

Author(s):

Bast, Hannah
Hert, Susan
dblp
dblp


Editor(s):

Bremner, David
dblp


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

URL of the conference:

http://www.cs.unb.ca/conf/cccg

URL for downloading the paper:


Event Address*:

Fredericton, New Brunswick, Canada
Language:

English

Event Date*
(no longer used):

August 16th - 19th
Organization:


Event Start Date:

17 October 2019
Event End Date:

17 October 2019

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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