On regular vertices of the union of planar convex objects
type: Item
instance of: scholarly article
title: On regular vertices of the union of planar convex objects
zbMATH Open document ID: 1167.52002
author: Esther Ezra
author: János Pach
author: Micha Sharir
published in: Discrete \& Computational Geometry
publication date: 2009-05-13T00:00:00Z
review text: Let \(\mathcal{C}\) be a collection of \(n\) compact convex sets in the plane such that the boundaries of any pair of sets in \(\mathcal{C}\) intersect in at most \(s\) points for some constant \(s\geq 4\). Let \(U\) denote the union of \(\mathcal{C}\). If the boundaries of a pair of sets in \(\mathcal{C}\) intersect exactly twice, their two intersection points are called regular. Several recent papers have considered the problem of obtaining bounds on the number of regular intersection points that can appear on the boundary of \(U\). The authors show that for each \(\varepsilon>0\) there is a constant \(C_\varepsilon\) such that the maximum number of regular intersection points of \(\mathcal{C}\) which belong to the boundary of \(U\) is \(\leq C_\varepsilon n^{\frac43+\varepsilon}\). This result improves earlier bounds from \textit{B. Aronov, A. Efrat, D. Halperin} and \textit{M. Sharir} [Discrete Comput. Geom. 25, No.~2, 203--220 (2001; Zbl 0996.68215)]. The bound is nearly tight in the worst case.
Mathematics Subject Classification ID: 52A10
zbMATH DE Number: 5553476
zbMATH Keywords: bi-clique decomposition
zbMATH Keywords: compact convex sets
zbMATH Keywords: geometric arrangements
zbMATH Keywords: lower envelopes
reviewed by: Mikhail Ostrovskii
MaRDI profile type: Publication
full work available at URL: s00454-008-9118-2
OpenAlex ID: W2085954234
cites work: Q3997899
cites work: Q4225298
cites work: Pseudo-Line Arrangements: Duality, Algorithms, and Applications
cites work: Q4875176
cites work: On the number of regular vertices of the union of Jordan regions
cites work: A deterministic view of random sampling and its use in geometry
cites work: Q3772828
cites work: Counting and representing intersections among triangles in three dimensions
cites work: An Expander-Based Approach to Geometric Optimization
cites work: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
cites work: Cutting hyperplane arrangements
cites work: On the boundary of the union of planar convex sets
cites work: Q4657590
cites work: Q4325546
DOI: 10.1007/S00454-008-9118-2
description: scientific article; zbMATH DE number 5553476