English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  The Area Partitioning Problem

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3405-A Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3406-8
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Bast, Hannah1, Author           
Hert, Susan1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-022000
 Publication Status: Issued
 Pages: -
 Publishing info: Fredericton, Canada : University of New Brunswick
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518098
Other: Local-ID: C1256428004B93B8-CB8B3D8779E38E64C12569D80065B9AC-bh-app-00
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Fredericton, New Brunswick, Canada
Start-/End Date: 2000

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG-00)
Source Genre: Proceedings
 Creator(s):
Bremner, David, Editor
Affiliations:
-
Publ. Info: Fredericton, Canada : University of New Brunswick
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 163 - 171 Identifier: -