The Area Partitioning Problem

Bast, Hannah; Hert, Susan

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 公開

表示: 全項目非表示: 全項目

基本情報

表示: 非表示:

アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-3405-A 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-3406-8

資料種別: 会議論文

ファイル

表示: ファイル

作成者

表示:

非表示:

作成者:
Bast, Hannah¹, 著者
Hert, Susan¹, 著者

所属:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

内容説明

表示:

非表示:

キーワード: -

要旨: 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.

資料詳細

表示:

非表示:

言語: eng - English

日付: 修正: 2010-03-02出版: 2000

出版の状態: 出版

ページ: -

出版情報: Fredericton, Canada : University of New Brunswick

目次: -

査読: -

識別子（DOI, ISBNなど）: eDoc: 518098
その他: Local-ID: C1256428004B93B8-CB8B3D8779E38E64C12569D80065B9AC-bh-app-00

学位: -

訴訟

表示:

Project information

表示:

出版物 1

表示:

非表示:

出版物名: Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG-00)

種別: 会議論文集

著者・編者:
Bremner, David, 編集者

所属:
-

出版社, 出版地: Fredericton, Canada : University of New Brunswick

ページ: - 巻号: - 通巻号: - 開始・終了ページ: 163 - 171 識別子（ISBN, ISSN, DOIなど）: -

アイテム詳細

基本情報

ファイル

関連URL

作成者

内容説明

資料詳細

関連イベント

訴訟

Project information

出版物 1