{
  "abstract": "The Union Volume Estimation problem, i.e. yielding an $(\\varepsilon, \\delta)$-approximation of the volume of the union of convex bodies, is a classical problem in computational geometry and formal methods. In this paper, we first detect where and why the efficient union volume estimators with approximate sampling and PAC volume estimation oracles fail. Specifically, we show that having only TV-distance guarantees on the approximate sampler does not suffice, and demonstrate this bottleneck by constructing the sunflower families of convex bodies. In this context, we propose the concept of tail-controlled samplers that can yield with high-probability almost-$\\ell_{\\infty}$ closeness. Secondly, we leverage this concept to propose a generic algorithmic framework Alpona that properly combines a PAC volume computation and approximate point sampling oracles with tail-controls to yield an $(\\varepsilon, \\delta)$-estimate of the union volume for any collection of convex bodies. We show that Alpona needs only linear (in number of convex bodies) oracle calls to be $(\\varepsilon, \\delta)$-correct. Finally, we provide a tail-controlled analysis of the Hit-and-Run sampler [Lovász and Vempala, 2006]. We further provide a novel geometric analysis to improve the required walk length of Hit-and-Run. We further instantiate Alpona's correctness for the sparse frequency streams of convex bodies: a special case of the union volume estimation problem where no convex body intersects more than $\\tau$ many other bodies.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2611.06364",
  "author_total": 6,
  "authors": [
    {
      "name": "Eeshan Banerjee"
    },
    {
      "name": "Aranya Kumar Bal"
    },
    {
      "name": "Debabrota Basu"
    },
    {
      "name": "Sourav Chakraborty"
    },
    {
      "name": "Debarshi Chanda"
    },
    {
      "name": "Uddalok Sarkar"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/8dz94m7k7m424.bib",
  "cited_by": 0,
  "doi": null,
  "fulltext_url": null,
  "id": "8dz94m7k7m424",
  "issns": [],
  "landing_url": "https://hal.science/hal-05855047v1",
  "language": "en",
  "licence": "CC-BY-NC-4.0",
  "licence_label": "CC BY-NC 4.0",
  "licence_source": "article",
  "licence_url": "https://creativecommons.org/licenses/by-nc/4.0/",
  "metadata_licence": null,
  "native_subjects": [
    [
      "hal",
      "0.info"
    ],
    [
      "hal",
      "0.math"
    ],
    [
      "hal",
      "0.stat"
    ],
    [
      "hal",
      "1.info.info-cg"
    ],
    [
      "hal",
      "1.info.info-ds"
    ],
    [
      "hal",
      "1.math.math-st"
    ],
    [
      "hal",
      "1.stat.ot"
    ]
  ],
  "openalex": null,
  "pdf_url": "https://hal.science/hal-05855047/document",
  "pmcid": null,
  "pmid": null,
  "published": "2026-11-04",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/8dz94m7k7m424.ris",
  "sources": [
    {
      "first_seen": "2026-11-07T12:20:25Z",
      "native_id": "hal-05855047",
      "source": "hal",
      "url": "https://hal.science/hal-05855047v1"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "hal:0.stat",
      "subfield": "statistics"
    }
  ],
  "title": "Estimating the Volume of a Union of Convex Bodies",
  "title_text": "Estimating the Volume of a Union of Convex Bodies",
  "type": "preprint",
  "updated_at": "2026-11-08T12:20:49Z",
  "url": "https://research.draconitic.com/paper/8dz94m7k7m424",
  "venue": "HAL",
  "versions": []
}