Inclusion-exclusion complexes for pseudodisk collections
type: Item
instance of: scholarly article
title: Inclusion-exclusion complexes for pseudodisk collections
zbMATH Open document ID: 0877.68108
DOI: 10.1007/PL00009295
published in: Discrete \& Computational Geometry
publication date: 1997-11-17T00:00:00Z
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)].
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 52C35
zbMATH DE Number: 1011310
zbMATH Keywords: inclusion-exclusion formulas
zbMATH Keywords: pseudodisk collections
zbMATH Keywords: area computation
zbMATH Keywords: topological sweep
author: Herbert Edelsbrunner
author: Edgar A. Ramos
reviewed by: Günter M. Ziegler
MaRDI profile type: Publication
cites work: Q4003411
cites work: The union of balls and its dual shape
cites work: Q5786239
cites work: Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
cites work: Q5663020
cites work: \(\epsilon\)-nets and simplex range queries
cites work: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
cites work: The area of intersection of n equal circular disks
cites work: Q3827224
cites work: Inclusion-exclusion-Bonferroni identities and inequalities for discrete tube-like problems via Euler characteristics
cites work: Q4011326
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
description: scientific article; zbMATH DE number 1011310