The combinatorial encoding of disjoint convex sets in the plane
type: Item
instance of: scholarly article
title: The combinatorial encoding of disjoint convex sets in the plane
zbMATH Open document ID: 1174.52001
author: Jacob E. Goodman
author: Richard Pollack
published in: Combinatorica
publication date: 2008-10-21T00:00:00Z
review text: The authors introduce the following combinatorial encoding for a planar family \(\mathcal{C}=\{ C_1,\dots, C_n\}\) of mutually disjoint compact convex sets: Project the members of \(\mathcal {C}\) onto a directed line \(L\) and denote the endpoints of each projected set \(C_i\) by \(i, i'\) according to their order on \(L\). This gives a permutation of the \(2n\) indices \(1,\dots, n, 1',\dots, n'\). Then, rotate \(L\) counterclockwise and record the circular sequence consisting of all the ``double permutations'' of \(1,\dots,n\) arising in this way. Using this encoding, the authors give a new proof of the \textit{H. Edelsbrunner}-\textit{M. Sharir} theorem [Discrete Comput. Geom. 5, No. 1, 35--42 (1990; Zbl 0712.52009)] which asserts that a planar family of \(n\) compact convex sets cannot be met by straight lines in more than \(2n-2\) combinatorially distinct ways. Moreover, the Edelsbrunner-Sharir theorem is extended from families of compact convex sets to families of compact connected sets.
Mathematics Subject Classification ID: 52A10
Mathematics Subject Classification ID: 52A35
Mathematics Subject Classification ID: 52C30
zbMATH DE Number: 5355085
zbMATH Keywords: planar convex sets
zbMATH Keywords: double-permutation sequence
zbMATH Keywords: geometric permutation
zbMATH Keywords: pseudoline arrangement
reviewed by: Mircea Balaj
MaRDI profile type: Publication
full work available at URL: s00493-008-2239-7
OpenAlex ID: W1994263951
cites work: Q5290252
cites work: Oriented Matroids
cites work: Q4274009
cites work: The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
cites work: Proof of a conjecture of Burr, Grünbaum, and Sloane
cites work: On the combinatorial classification of nondegenerate configurations in the plane
cites work: Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines
cites work: Q3138749
cites work: Arrangements and Topological Planes
cites work: Q5663020
cites work: Geometric permutations for convex sets
cites work: Q4657586
cites work: On the number of balanced lines
cites work: Q4325546
DOI: 10.1007/S00493-008-2239-7
Recommended article: Q5490271
Recommended article: A convex combinatorial property of compact sets in the plane and its roots in lattice theory
Recommended article: Combinatorial representation and convex dimension of convex geometries
Recommended article: Combinatorial properties of nonarchimedean convex sets
Recommended article: On separation of plane convex sets
Recommended article: On the discrepancy of convex plane sets
Recommended article: A generalisation of the Erdős-Szekeres theorem to disjoint convex sets
Recommended article: Q5872933
Recommended article: Q3787039
Recommended article: Convexity in combinatorial structures
description: scientific article; zbMATH DE number 5355085