MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Hert, Susandblp
Editor(s):
BibTeX cite key*:
h-cap-01
Title, Booktitle
Title*:
Connected Area Partitioning
Booktitle*:
Proceedings of the 17th European Workshop on Computational Geometry (CG-01)
Event, URLs
Conference URL::
http://www.inf.fu-berlin.de/~cg01/
Downloading URL:
Event Address*:
Berlin, Germany
Language:
English
Event Date*
(no longer used):
March, 26 - 28, 2001
Organization:
Event Start Date:
18 April 2021
Event End Date:
18 April 2021
Publisher
Name*:
Freie Universität Berlin
URL:
Address*:
Berlin, Germany
Type:
Extended Abstract
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
March
Pages:
35-38
Year*:
2001
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
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.
Keywords:
Motion Planning, Robotics, Polygon Partitioning
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, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{h-cap-01,
AUTHOR = {Hert, Susan},
TITLE = {Connected Area Partitioning},
BOOKTITLE = {Proceedings of the 17th European Workshop on Computational Geometry (CG-01)},
PUBLISHER = {Freie Universität Berlin},
YEAR = {2001},
TYPE = {Extended Abstract},
PAGES = {35--38},
ADDRESS = {Berlin, Germany},
MONTH = {March},
}


Entry last modified by Anja Becker, 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
08/02/2001 09:31:36 AM
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Susan Hert
Susan Hert

Edit Dates
08.04.2002 13:02:40
02/08/2001 10:01:01
02/08/2001 09:31:37