HEXAGONbeta

Universal Support Theorems for Resilient Coverage

A mix of human-written and AI-generated textHuman understanding: all partscs.CG — Computational Geometrymath.CO — Combinatorics

Contributed by Deep Bhattacharjee ↗, Ushashi Bhattacharya ↗, Sanjeevan Singha Roy ↗

Version 1 / Oct 29, 2026 / CC BY 4.0

Abstract

We prove that one finite set of points decides whether sensors cover a polygonal target under every failure rule in which an extra working sensor never hurts. The set is the same for every such rule, and on a face of dimension f the weakest point is fixed by f+1 sensors. The theorem holds in any dimension for functions that share a convex part and differ by affine terms. For sensing disks it gives the exact radius and power that keep the target covered under each rule, as rational numbers, the full trade-off between radius and budget, the smallest list of sensor groups whose loss breaks coverage, exact tests under independent placement errors, and protection plans proved optimal by a matching dual certificate.

Provenance statement

Tools: OpenAI Codex, Anthropic Claude / Claude Code, Python (fractions, numpy, matplotlib for the figures), LaTeX / pdfLaTeX with REVTeX 4.2 and TikZ. Archive: release v1.1.1 of https://github.com/creelie/sensor-resilience-certificates , DOI https://doi.org/10.5281/zenodo.23742526.
AI provenance filesAI_PROVENANCE.md · 1 KB

Tools used

OpenAI
ChatGPTVersion GPT-6.1 SOL Ultra

References

  1. D. Bhattacharjee and U. Bhattacharya, Iterated Nerve Complexes for kk-Fold Sensor Coverage , Preprints.org, version 2, 2026. doi:10.20944/preprints202606.1351.v2 (https://doi.org/10.20944/preprints202606.1351.v2).DOI
  2. A. Bose, D. Bhattacharjee and U. Bhattacharya, Certified Redundant ECoG Coverage: Exact Geometry, Continuous Mesh Certificates and Reproducible Audits , research and software archive, version 1.6.0, Zenodo, 2026. doi:10.5281/zenodo.23731783 (https://doi.org/10.5281/zenodo.23731783).DOI
  3. D. R. Sheehy, A multicover nerve for geometric inference , Proceedings of the 24th Canadian Conference on Computational Geometry, Charlottetown, 2012. https://mathtube.org/sites/default/files/lecture-notes/e-proceedings.pdf.link
  4. R. Corbet, M. Kerber, M. Lesnick and G. Osang, Computing the multicover bifiltration , Discrete Comput. Geom. 70 (2023), 376--405. doi:10.1007/s00454-022-00476-8 (https://doi.org/10.1007/s00454-022-00476-8).DOI
  5. Á. J. Alonso, A sparse multicover bifiltration of linear size , Discrete Comput. Geom., published online August 4, 2026. doi:10.1007/s00454-026-00865-3 (https://doi.org/10.1007/s00454-026-00865-3).DOI
  6. C. H. Dowker, Homology groups of relations , Ann. of Math. (2) 56 (1952), 84--95. doi:10.2307/1969768 (https://doi.org/10.2307/1969768).DOI
  7. S. Chowdhury and F. Mémoli, A functorial Dowker theorem and persistent homology of asymmetric networks , J. Appl. Comput. Topol. 2 (2018), 115--175. doi:10.1007/s41468-018-0020-6 (https://doi.org/10.1007/s41468-018-0020-6).DOI
  8. U. Bauer, M. Kerber, F. Roll and A. Rolle, A unified view on the functorial nerve theorem and its variations , Expo. Math. 41 (2023), no. 4, article 125503. doi:10.1016/j.exmath.2023.04.005 (https://doi.org/10.1016/j.exmath.2023.04.005).DOI
  9. R. Ghrist and A. Muhammad, Coverage and hole-detection in sensor networks via homology , Proceedings of IPSN 2005, IEEE, 2005, 254--260.
  10. V. de Silva and R. Ghrist, Coverage in sensor networks via persistent homology , Algebr. Geom. Topol. 7 (2007), 339--358. doi:10.2140/agt.2007.7.339 (https://doi.org/10.2140/agt.2007.7.339).DOI
Show all 29 referencesShow fewer references
  1. V. de Silva and R. Ghrist, Coordinate-free coverage in sensor networks with controlled boundaries via homology , Int. J. Robot. Res. 25 (2006), 1205--1222.
  2. J. Bochnak, M. Coste and M.-F. Roy, Real Algebraic Geometry , Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 36, Springer, Berlin, 1998. doi:10.1007/978-3-662-03718-8 (https://doi.org/10.1007/978-3-662-03718-8).DOI
  3. D. Bhattacharjee, Neuromorphic Grothendieck topoi for grid-embedded circuit architectures , SSRN, 2026. doi:10.2139/ssrn.6194939 (https://doi.org/10.2139/ssrn.6194939).DOI
  4. D. Bhattacharjee, Suspension of structures in two-dimensional topologies with or without the presence of X≥1\mathcal X\ge1 genus deformations for canonical 22η2^{2\eta} stabilizer points , Research Square, version 1, 2022. doi:10.21203/rs.3.rs-1798323/v1 (https://doi.org/10.21203/rs.3.rs-1798323/v1).DOI
  5. S. Singha Roy, D. Bhattacharjee and R. Sadhu, Instability in the linkage of topological spaces due to background ghosts , EPRA Int. J. Res. Dev. 8 (2023), no. 4, 276--279. doi:10.36713/epra13019 (https://doi.org/10.36713/epra13019).DOI
  6. E. Fogel, D. Halperin and R. Wein, CGAL Arrangements and Their Applications: A Step-by-Step Guide , Geometry and Computing, vol. 7, Springer, 2012. doi:10.1007/978-3-642-17283-0 (https://doi.org/10.1007/978-3-642-17283-0).DOI
  7. C.-F. Huang and Y.-C. Tseng, The coverage problem in a wireless sensor network , Proceedings of WSNA 2003, ACM, 2003, 115--121.
  8. X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless and C. Gill, Integrated coverage and connectivity configuration in wireless sensor networks , Proceedings of SenSys 2003, ACM, 2003, 28--39.
  9. R. E. Barlow and F. Proschan, Statistical Theory of Reliability and Life Testing: Probability Models , Holt, Rinehart and Winston, New York, 1975.
  10. B. Bollobás, D. Pritchard, T. Rothvoss and A. Scott, Cover-decomposition and polychromatic numbers , SIAM J. Discrete Math. 27 (2013), no. 1, 240--256. doi:10.1137/110856332 (https://doi.org/10.1137/110856332).DOI
  11. J.-L. Marichal, Weighted lattice polynomials , Discrete Math. 309 (2009), no. 4, 814--820. doi:10.1016/j.disc.2008.01.019 (https://doi.org/10.1016/j.disc.2008.01.019).DOI
  12. A. Dukhovny and J.-L. Marichal, System reliability and weighted lattice polynomials , Probab. Engrg. Inform. Sci. 22 (2008), no. 3, 373--388. doi:10.1017/S0269964808000223 (https://doi.org/10.1017/S0269964808000223).DOI
  13. A. Ben-Tal, L. El Ghaoui and A. Nemirovski, Robust Optimization , Princeton University Press, Princeton, 2009. doi:10.1515/9781400831050 (https://doi.org/10.1515/9781400831050).DOI
  14. T. Hailperin, Best possible inequalities for the probability of a logical function of events , Amer. Math. Monthly 72 (1965), no. 4, 343--359. doi:10.1080/00029890.1965.11970533 (https://doi.org/10.1080/00029890.1965.11970533).DOI
  15. B. Csikós, On the volume of flowers in space forms , Geom. Dedicata 86 (2001), 59--79. doi:10.1023/A:1011983123985 (https://doi.org/10.1023/A:1011983123985).DOI
  16. F. Aurenhammer, Power diagrams: properties, algorithms and applications , SIAM J. Comput. 16 (1987), no. 1, 78--96. doi:10.1137/0216006 (https://doi.org/10.1137/0216006).DOI
  17. G. T. Toussaint, Computing largest empty circles with location constraints , Int. J. Comput. Inf. Sci. 12 (1983), no. 5, 347--358. doi:10.1007/BF01008046 (https://doi.org/10.1007/BF01008046).DOI
  18. D.-T. Lee, On kk-nearest neighbor Voronoi diagrams in the plane , IEEE Trans. Comput. C-31 (1982), no. 6, 478--487. doi:10.1109/TC.1982.1676031 (https://doi.org/10.1109/TC.1982.1676031).DOI
  19. A. M.-C. So and Y. Ye, On solving coverage problems in a wireless sensor network using Voronoi diagrams , in: Internet and Network Economics (WINE 2005), Lecture Notes in Comput. Sci., vol. 3828, Springer, Berlin, 2005, 584--593. doi:10.1007/11600930_58 (https://doi.org/10.1007/11600930_58).DOI

Version history

  1. v1Submitted by Deep BhattacharjeeInitial depositCurrentOct 28, 2026