AreaCon

An open source C++ library for performing area-constrained partitioning operations on convex, 2D polygonal regions

Primary References

AreaCon is primarily a numerical implementation of the algorithms found in the following:


@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},
}
The algorithms used by AreaCon are also influenced by this work

@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}
}

Related Partitioning Concepts and Problems

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}
}

Computer Arithmetic and Numerical Methods

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,
}

Home

Documentation

References

Links

Wiki

FAQ

Contact