An open source C++ library for performing area-constrained partitioning operations on convex, 2D polygonal regions
AreaCon is primarily a numerical implementation of the algorithms found in the following:
The algorithms used by AreaCon are also influenced by this work@article{RP-PF-RB:13, author = {R. Patel and P. Frasca and F. Bullo}, title = {Centroidal Area-Constrained Partitioning for Robotic Networks}, journal = {ASME Journal of Dynamic Systems, Measurement, and Control}, year = 2014, volume = 136, number = 3, pages = 031024, keywords = {Robotic Networks}, abstract = {We consider the problem of optimal coverage with area-constraints in a mobile multi-agent system. For a planar environment with an associated density function, this problem is equivalent to dividing the environment into optimal subregions such that each agent is responsible for the coverage of its own region. In this paper, we design a continuous-time distributed policy which allows a team of agents to achieve a convex area-constrained partition of a convex workspace. Our work is related to the classic Lloyd algorithm, and makes use of generalized Voronoi diagrams. We also discuss practical implementation for real mobile networks. Simulation methods are presented and discussed.}, }
@InProceedings{RP-PF-FB:13conf, author = {R. Patel and P. Frasca and F. Bullo}, title = {Centroidal area-constrained partitioning for robotic networks}, booktitle = {ASME Dynamic Systems and Control Conference}, year = {2013}, month = October, address = {Stanford, CA, USA}, keywords = {Robotic Networks}, }
@article{JC:10,
author = {J. Cort{\'e}s},
title = {Coverage Optimization and Spatial Load Balancing by
Robotic Sensor Networks},
journal = {IEEE Transactions on Automatic Control},
year = 2010,
volume = 55,
number = 3,
pages = {749-754}
}
Information regarding basic geometric concepts that commonly appear in partitioning problems can be found here (the literature on partitioning is vast, so this is by no means an exhaustive list):
@book{AO-BB-KS-SNC:00, author = {A. Okabe and B. Boots and K. Sugihara and S. N. Chiu}, title = {Spatial Tessellations: Concepts and Applications of Voronoi Diagrams}, publisher = {Wiley and Sons}, year = 2000, series = {Wiley Series in Probability and Statistics}, edition = 2, ISBN = 0471986356, }
@book{FA-RK-DTL-RK:13, title={Voronoi diagrams and Delaunay triangulations}, author={Aurenhammer, F. and Klein, R. and Lee, D.T. and Klein, R.}, volume={8}, year={2013}, publisher={World Scientific} }
@article{QD-VF-MG:99, author = {Q. Du and V. Faber and M. Gunzburger}, title = {Centroidal {V}oronoi tessellations: {A}pplications and algorithms}, journal = {SIAM Review}, volume = 41, year = 1999, number = 4, pages = {637-676}, }
@article{DPB-SMR:15, title={Centroidal Power Diagrams, {L}loyd's Algorithm, and Applications to Optimal Location Problems}, author={Bourne, D.P. and Roper, S.M.}, journal={SIAM Journal on Numerical Analysis}, volume={53}, number={6}, pages={2545--2569}, year={2015}, publisher={SIAM} }
A few references regarding relevant partitioning problems in the context of dynamic coverage control in mobile robotics are found here:
@article{FB-RC-PF:08u, author = {F. Bullo and R. Carli and P. Frasca}, title = {Gossip Coverage Control for Robotic Networks: {D}ynamical Systems on the Space of Partitions}, journal = {SIAM Journal on Control and Optimization, year = 2012, volume = 50, number = 1, pages = {419-447}, keyword = "Robotic Networks", }
@article{MP-AA-EF-FB:11, title={Distributed algorithms for environment partitioning in mobile robotic networks}, author={Pavone, M. and Arsie, A. and Frazzoli, E. and Bullo, F.}, journal={Automatic Control, IEEE Transactions on}, volume={56}, number={8}, pages={1834--1848}, year={2011}, publisher={IEEE} }
@article{JGC-EC-RD:12, title={Shadow prices in territory division}, author={Carlsson, J.G. and Carlsson, E. and Devulapalli, R.}, journal={Networks and Spatial Economics}, pages={1--39}, year={2012}, publisher={Springer} }
Information regarding basic geometric concepts that commonly appear in partitioning problems can be found here (the literature on partitioning is vast, so this is by no means an exhaustive list):
@book{DRK-EWC:02, title={Numerical Analysis: Mathematics of Scientific Computing}, author={Kincaid, D.R. and Cheney, E.W.}, volume={2}, year={2002}, publisher={American Mathematical Society}, isbn={9780821847886} }
@Book{UMA-LRP:98, author = {U. M. Ascher and L. R. Petzold}, title = {Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations}, publisher = SIAM, year = 1998, ISBN = 0898714125, }