Algorithms for fair partitioning of convex polygons

被引：5

作者：

Armaselu, Bogdan ^{[1
]}

Daescu, Ovidiu ^{[1
]}

机构：

[1] Univ Texas Dallas, Dept Comp Sci, Richardson, TX 75083 USA

来源：

THEORETICAL COMPUTER SCIENCE | 2015年 / 607卷

关键词：

Algorithm; Fair partitioning; Convex polygon;

D O I：

10.1016/j.tcs.2015.08.003

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we study the problem of partitioning a convex polygon P of n vertices into m polygons of equal area and perimeter. We give an algorithm for m = 2 that runs in 0(n) time, and an algorithm for m = 2(k), where k is an integer, that runs in O ((2n)(k)) time. These are the first algorithms to solve this problem. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：351 / 362

页数：12

共 11 条

[1] [Anonymous], 1983, Computational Geometry, Advances in Computing Research
[2] Barany I., 2009, EQUIPARTITIONING CON
[3] Bereg S., 2003, P JAP C DISCR COMP G, P72
[4] Bereg S., 2002, JCDCG, P60
[5] HERTEL S, 1983, LECT NOTES COMPUT SC, V158, P207
[6] Hubard A., 2011, CONVEX EQUIPARTITION
[7] Karasev R.N., 2010, EQUIPARTITION SEVER
[8] Fair partitions of polygons: An elementary introduction
Nandakumar, R.
Rao, N. Ramana
[J]. PROCEEDINGS OF THE INDIAN ACADEMY OF SCIENCES-MATHEMATICAL SCIENCES, 2012, 122 (03): : 459 - 467
[9] Nandakumar R., 2010, FAIR PARTITIONING PO
[10] Steinhaus H., 1999, Mathematical Snapshots, V3rd, P64

← 1 2 →