{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:30:31Z","timestamp":1750307431242,"version":"3.41.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,8,1]],"date-time":"2010-08-01T00:00:00Z","timestamp":1280620800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,8]]},"abstract":"<jats:p>\n            Previous work has developed algorithms for finding an equitable convex partition that partitions the plane into\n            <jats:italic>n<\/jats:italic>\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\n            <jats:italic>exact<\/jats:italic>\n            solution to our problem in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>N n<\/jats:italic>\n            log\n            <jats:italic>N<\/jats:italic>\n            ) time or operations, where\n            <jats:italic>n<\/jats:italic>\n            is the number of points,\n            <jats:italic>m<\/jats:italic>\n            the number of vertices or edges of the polygon, and\n            <jats:italic>N<\/jats:italic>\n            :=\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            the sum.\n          <\/jats:p>","DOI":"10.1145\/1824777.1824792","type":"journal-article","created":{"date-parts":[[2010,9,2]],"date-time":"2010-09-02T13:14:24Z","timestamp":1283433264000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Finding equitable convex partitions of points in a polygon efficiently"],"prefix":"10.1145","volume":"6","author":[{"given":"John Gunnar","family":"Carlsson","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA"}]},{"given":"Benjamin","family":"Armbruster","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}]},{"given":"Yinyu","family":"Ye","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}]}],"member":"320","published-online":{"date-parts":[[2010,9,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-001-0003-5"},{"volume-title":"Proceedings of the 12th Canadian Conference on Computational Geometry. 163--171","author":"Bast H.","key":"e_1_2_1_2_1","unstructured":"Bast , H. and Hert , S . 2000. The area partitioning problem . In Proceedings of the 12th Canadian Conference on Computational Geometry. 163--171 . Bast, H. and Hert, S. 2000. The area partitioning problem. In Proceedings of the 12th Canadian Conference on Computational Geometry. 163--171."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034095"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.06.003"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s4540010065"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2004.11920050"},{"volume-title":"Proceedings of the Fields Institute Workshop on Global Optimization, P. M. Pardalas and T. F. Coleman, Eds. The Fields Institute Comm. 55","author":"Carlsson J. G.","key":"e_1_2_1_7_1","unstructured":"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 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"},{"volume-title":"Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG'05)","author":"Carmi P.","key":"e_1_2_1_8_1","unstructured":"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. 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."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195998000230"},{"key":"e_1_2_1_10_1","volume-title":"Japanese Conference, (JCDCG'98)","volume":"1763","author":"Ito","year":"1998","unstructured":"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. 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."},{"volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation. IEEE","author":"J\u00e4ger M.","key":"e_1_2_1_11_1","unstructured":"J\u00e4ger , 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. J\u00e4ger, 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."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/646320.686388"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2808-2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.4.4.435"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003730200011"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176991596"},{"key":"e_1_2_1_17_1","first-page":"26","article-title":"A note on the ham sandwich theorem","volume":"11","author":"Steinhaus H.","year":"1938","unstructured":"Steinhaus , H. 1938 . A note on the ham sandwich theorem . Mathesis Polska 11 , 26 -- 28 . translated in Beyer and Zardecki {2004}. Steinhaus, H. et al. 1938. A note on the ham sandwich theorem. Mathesis Polska 11, 26--28. translated in Beyer and Zardecki {2004}.","journal-title":"Mathesis Polska"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1824777.1824792","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1824777.1824792","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:53Z","timestamp":1750246793000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1824777.1824792"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["10.1145\/1824777.1824792"],"URL":"https:\/\/doi.org\/10.1145\/1824777.1824792","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2010,8]]},"assertion":[{"value":"2007-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-09-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}