Inclusion-exclusion complexes for pseudodisk collections

DOI10.1007/PL00009295MaRDI QIDQ1355193zbMATH OpenFDO

Authors Herbert Edelsbrunner, Edgar A. Ramos

Publication date 17 November 1997

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/PL00009295

zbMATH Keywords

area computationinclusion-exclusion formulaspseudodisk collectionstopological sweep

Mathematics Subject Classification ID

Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

For any finite collection of pseudodisks in the plane (topological disks whose pairwise intersections are either disks or empty) the area can be computed by inclusion-exclusion as \[ \mu(\bigcup B)=\sum_{\sigma\in\Delta}(-1)^{|\sigma|-1}\mu(\bigcap\sigma), \] where \(\Delta\) is an abstract \(2\)-dimensional nerve complex that can be nicely embedded into the interior of the collection. The proof of the result and the algorithm for the computation of such a nerve complex depends on a topological sweep, and therefore they do not generalize to higher dimensions. The paper contains a nice example of a pseudodisk collection that is not equivalent to a collection of geometric disks. It remains an open problem whether analogous results are valid in higher dimensions, as they are for arrangements of geometric balls, due to \textit{H. Edelsbrunner} [``The union of balls and its dual shape, in: ``The László Fejes Tóth Festschrift (I. Bárány, J. Pach, eds.), Discrete Comput. Geom. 13, No. 3-4, 415-440 (1995; Zbl 0826.68053)].

Recommendations

• Inclusion-exclusion formulas from independent complexes
• Multiple covers with balls. I: Inclusion-exclusion
• Combinatorial complexity of signed discs
• On pseudo-disk hypergraphs

Cites work

• -nets and simplex range queries
• scientific article; zbMATH DE number 4102053 (Why is no real title available?)
• scientific article; zbMATH DE number 53152 (Why is no real title available?)
• scientific article; zbMATH DE number 66691 (Why is no real title available?)
• scientific article; zbMATH DE number 3394958 (Why is no real title available?)
• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• Inclusion-exclusion-Bonferroni identities and inequalities for discrete tube-like problems via Euler characteristics
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• The area of intersection of n equal circular disks
• The union of balls and its dual shape
• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)

Cited in

(6)

• Simplifying Inclusion–Exclusion Formulas
• Arrangements of pseudocircles: on circularizability
• Arrangements of pseudocircles: on circularizability
• Some Cardinal Estimations via the Inclusion-Exclusion Principle in Finite $$T_0$$ Topological Spaces
• A note on Zeilberger's abstract lace expansion
• Arrangements of pseudocircles and circles

This page was built for publication: Inclusion-exclusion complexes for pseudodisk collections

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1355193)