More Web Proxy on the site http://driver.im/

research-article

Finding equitable convex partitions of points in a polygon efficiently

Authors:

John Gunnar Carlsson,

Benjamin Armbruster,

Yinyu YeAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 6, Issue 4

Article No.: 72, Pages 1 - 19

https://doi.org/10.1145/1824777.1824792

Published: 03 September 2010 Publication History

Abstract

Previous work has developed algorithms for finding an equitable convex partition that partitions the plane into n convex pieces each containing an equal number of red and blue points. Motivated by a vehicle routing heuristic, we look at a related problem where each piece must contain one point and an equal fraction of the area of some convex polygon. We first show how algorithms for solving the older problem lead to approximate solutions for this new equitable convex partition problem. Then we demonstrate a new algorithm that finds an exact solution to our problem in O(N nlog N) time or operations, where n is the number of points, m the number of vertices or edges of the polygon, and N:=n+m the sum.

References

[1]

Bárány, I. and Matoušek, J. 2001. Simultaneous partitions of measures by k-fans. Discr. Comput. Geom. 25, 3, 317--334.

Digital Library

[2]

Bast, H. and Hert, S. 2000. The area partitioning problem. In Proceedings of the 12th Canadian Conference on Computational Geometry. 163--171.

[3]

Beardwood, J., Halton, J. H., and Hammersley, J. M. 1959. The shortest path through many points. Proc. Cambridge Phil. Soc. 55, 299--327.

[4]

Bereg, S., Bose, P., and Kirkpatrick, D. 2006. Equitable subdivisions within polygonal regions. Comput. Geom. 34, 20--27.

Digital Library

[5]

Bespamyatnikh, S., Kirkpatrick, D., and Snoeyink, J. 2000. Generalizing ham sandwich cuts to equitable subdivisions. Discr. Comput. Geom. 24, 4, 605--622.

Digital Library

[6]

Beyer, W. A. and Zardecki, A. 2004. The early history of the ham sandwich theorem. Amer. Math. Month. 111, 1, 58--61.

[7]

Carlsson, J. G., Ge, D., Subramaniam, A., Wu, A., and Ye, Y. 2007. Solving min-max multi-depot vehicle routing problem. In Proceedings of the Fields Institute Workshop on Global Optimization, P. M. Pardalas and T. F. Coleman, Eds. The Fields Institute Comm. 55. 31--46

[8]

Carmi, P. and Katz, M. 2005. Minimum-cost load-balancing partitions. In Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG'05). 63--65.

[9]

Hert, S. and Lumelsky, V. 1998. Polygon area decomposition for multiple-robot workspace division. Int. J. Comput. Geom. Appl. 8, 4, 437--466.

[10]

Ito, Uehara, and Yokoyama. 1998. 2-dimension ham sandwich theorem for partitioning into three convex pieces. In Discrete and Computational Geometry, Japanese Conference, (JCDCG'98). Revised Papers, J. Akiyama, M. Kano, and M. Urabe, Eds. Lecture Notes in Computer Science, vol. 1763. Springer, 129--157.

Digital Library

[11]

Jäger, M. and Nebel, B. 2002. Dynamic decentralized area partitioning for cooperating cleaning robots. In Proceedings of the IEEE International Conference on Robotics and Automation. IEEE, Los Alamitos, CA, 3577--3582.

[12]

Kaneko, A. and Kano, M. 2001. Generalized balanced partitions of two sets of points in the plane. In Discrete and Computational Geometry. Lecture Notes in Computer Science, vol. 2098. 176--186.

Digital Library

[13]

Kaneko, A. and Kano, M. 2002. Perfect partitions of convex sets in the plane. Discr. Compuat. Geom. 28, 211--222.

Digital Library

[14]

Koutsoupias, E., Papadimitriou, C. H., and Sideri, M. 1992. On the optimal bisection of a polygon. ORSA J. Comput. 4, 4, 435--438.

[15]

Sakai, T. 2002. Balanced convex partitions of measure in R². Graphs Combin. 18, 169--192.

[16]

Steele, J. M. 1988. Growth rates of Euclidean minimal spanning trees with power weighted edges. Ann. Probab. 16, 1767--1787.

[17]

Steinhaus, H. et al. 1938. A note on the ham sandwich theorem. Mathesis Polska 11, 26--28. translated in Beyer and Zardecki {2004}.

Cited By

Tsai FYang JLuo B(2022)Continuance Intention of Online Healthcare CommunitiesJournal of Organizational and End User Computing10.4018/JOEUC.30289234:7(1-25)Online publication date: 12-May-2022
https://dl.acm.org/doi/10.4018/JOEUC.302892
Li LCai XHe XYu XLi HLiu Y(2022)Individual Decision Model for Using Technology of Health Crowdsensing in the Digital EraJournal of Organizational and End User Computing10.4018/JOEUC.30265134:7(1-21)Online publication date: 15-Jun-2022
https://dl.acm.org/doi/10.4018/JOEUC.302651
Chen CDu YGe DLei LYe Y(2022)Optimization and Operations Research in Mitigation of a PandemicJournal of the Operations Research Society of China10.1007/s40305-022-00391-y10:2(289-304)Online publication date: 11-May-2022
https://doi.org/10.1007/s40305-022-00391-y
Show More Cited By

Index Terms

Finding equitable convex partitions of points in a polygon efficiently
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Computing Balanced Convex Partitions of Lines
Abstract
Dujmović and Langerman (Discrete Comput Geom 49(1):74–88, 2013) proved a ham-sandwich cut theorem for an arrangement of lines in the plane. Recently, Xue and Soberón (Discrete Comput Geom 66:1150–1167, 2021) generalized it to balanced convex ...
Finding the convex hull of a simple polygon

We describe a new algorithm for finding the convex hull of any simple polygon specified by a sequence of m vertices. An earlier convex hull finder of ours is limited to polygons which remain simple (i.e., nonselfintersecting) when locally non-convex ...
A historical note on convex hull finding algorithms

Most of the progress made on the convex hull problem has been accomplished during and after the late 1970's. In the convex hull literature to date, Graham (1972) is credited with the first optimal O(n log n) algorithm for computing the convex hull of n ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 6, Issue 4

August 2010

308 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1824777

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 September 2010

Accepted: 01 November 2007

Received: 01 October 2007

Published in TALG Volume 6, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
505
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tsai FYang JLuo B(2022)Continuance Intention of Online Healthcare CommunitiesJournal of Organizational and End User Computing10.4018/JOEUC.30289234:7(1-25)Online publication date: 12-May-2022
https://dl.acm.org/doi/10.4018/JOEUC.302892
Li LCai XHe XYu XLi HLiu Y(2022)Individual Decision Model for Using Technology of Health Crowdsensing in the Digital EraJournal of Organizational and End User Computing10.4018/JOEUC.30265134:7(1-21)Online publication date: 15-Jun-2022
https://dl.acm.org/doi/10.4018/JOEUC.302651
Chen CDu YGe DLei LYe Y(2022)Optimization and Operations Research in Mitigation of a PandemicJournal of the Operations Research Society of China10.1007/s40305-022-00391-y10:2(289-304)Online publication date: 11-May-2022
https://doi.org/10.1007/s40305-022-00391-y
Shi WLi QZhang RShen GJiang YYuan ZMuntean GShen HZhuang YSmith JYang YCesar PMetze FPrabhakaran B(2021)QoE Ready to Respond: A QoE-aware MEC Selection Scheme for DASH-based Adaptive Video Streaming to Mobile UsersProceedings of the 29th ACM International Conference on Multimedia10.1145/3474085.3475325(4016-4024)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1145/3474085.3475325
Behroozi MCarlsson J(2020)Computational Geometric Approaches to Equitable Districting: A SurveyOptimal Districting and Territory Design10.1007/978-3-030-34312-5_4(57-74)Online publication date: 5-Feb-2020
https://doi.org/10.1007/978-3-030-34312-5_4
Zhang WMo ZChen CZheng Q(2014)CBCMultimedia Tools and Applications10.5555/2687511.268755973:3(1663-1686)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.5555/2687511.2687559
(2013)Dividing a Territory Among Several FacilitiesINFORMS Journal on Computing10.5555/2700769.270078025:4(730-742)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.5555/2700769.2700780
Carlsson JDevulapalli R(2013)Dividing a Territory Among Several FacilitiesINFORMS Journal on Computing10.1287/ijoc.1120.053625:4(730-742)Online publication date: Nov-2013
https://doi.org/10.1287/ijoc.1120.0536
Carlsson JCarlsson EDevulapalli R(2013)Balancing workloads of service vehicles over a geographic territory2013 IEEE/RSJ International Conference on Intelligent Robots and Systems10.1109/IROS.2013.6696355(209-216)Online publication date: Nov-2013
https://doi.org/10.1109/IROS.2013.6696355
Venkata Narasimha KKivelevitch ESharma BKumar M(2013)An ant colony optimization technique for solving min–max Multi-Depot Vehicle Routing ProblemSwarm and Evolutionary Computation10.1016/j.swevo.2013.05.00513(63-73)Online publication date: Dec-2013
https://doi.org/10.1016/j.swevo.2013.05.005
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents