The combinatorial encoding of disjoint convex sets in the plane

by: Jacob Goodman, Richard Pollack

Combinatorica, Vol. 28, No. 1. (30 January 2008), pp. 69-81.

View FullText article

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

AbnerCYH

Find related articles with these CiteULike tags

combinatorics, geometries

Abstract

Abstract We introduce a new combinatorial object, the double-permutation sequence, and use it to encode a family of mutually disjoint compact convex sets in the plane in a way that captures many of its combinatorial properties. We use this encoding to give a new proof of the Edelsbrunner-Sharir theorem that a collection of n compact convex sets in the plane cannot be met by straight lines in more than 2n-2 combinatorially distinct ways. The encoding generalizes the authors’ encoding of point configurations by “allowable sequences” of permutations. Since it applies as well to a collection of compact connected sets with a specified pseudoline arrangement $$ \mathcalA $$ of separators and double tangents, the result extends the Edelsbrunner-Sharir theorem to the case of geometric permutations induced by pseudoline transversals compatible with $$ \mathcalA $$.

@article{citeulike:2760322, abstract = {Abstract\ \ We introduce a new combinatorial object, the double-permutation sequence, and use it to encode a family of mutually disjoint compact convex sets in the plane in a way that captures many of its combinatorial properties. We use this encoding to give a new proof of the Edelsbrunner-Sharir theorem that a collection of n compact convex sets in the plane cannot be met by straight lines in more than 2n-2 combinatorially distinct ways. The encoding generalizes the authors’ encoding of point configurations by “allowable sequences” of permutations. Since it applies as well to a collection of compact connected sets with a specified pseudoline arrangement \$\$ \mathcal{A} \$\$ of separators and double tangents, the result extends the Edelsbrunner-Sharir theorem to the case of geometric permutations induced by pseudoline transversals compatible with \$\$ \mathcal{A} \$\$.}, author = {Goodman, Jacob and Pollack, Richard }, citeulike-article-id = {2760322}, doi = {10.1007/s00493-008-2239-7}, journal = {Combinatorica}, keywords = {combinatorics, geometries}, month = {January}, number = {1}, pages = {69--81}, posted-at = {2008-05-06 10:20:39}, priority = {2}, title = {The combinatorial encoding of disjoint convex sets in the plane}, url = {http://dx.doi.org/10.1007/s00493-008-2239-7}, volume = {28}, year = {2008} }

RIS record

TY - JOUR ID - citeulike:2760322 L3 - citeulike-article-id:2760322 TI - The combinatorial encoding of disjoint convex sets in the plane JF - Combinatorica VL - 28 IS - 1 SP - 69 EP - 81 N2 - Abstract  We introduce a new combinatorial object, the double-permutation sequence, and use it to encode a family of mutually disjoint compact convex sets in the plane in a way that captures many of its combinatorial properties. We use this encoding to give a new proof of the Edelsbrunner-Sharir theorem that a collection of n compact convex sets in the plane cannot be met by straight lines in more than 2n-2 combinatorially distinct ways. The encoding generalizes the authors’ encoding of point configurations by “allowable sequences” of permutations. Since it applies as well to a collection of compact connected sets with a specified pseudoline arrangement $$ \mathcal{A} $$ of separators and double tangents, the result extends the Edelsbrunner-Sharir theorem to the case of geometric permutations induced by pseudoline transversals compatible with $$ \mathcal{A} $$. KW - combinatorics KW - geometries AU - Goodman, Jacob AU - Pollack, Richard PY - 2008/01/30/ UR - http://dx.doi.org/10.1007/s00493-008-2239-7 ER -

RIS BibTeX