Name
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}$$ . |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s00493-008-2239-7 | Combinatorica |
Keywords | Field | DocType |
disjoint convex set,compact connected set,edelsbrunner-sharir theorem,n compact convex set,encoding generalizes,new proof,combinatorial encoding,pseudoline transversals,new combinatorial object,specified pseudoline arrangement,combinatorial property,disjoint compact convex set,convex set | ENCODE,Discrete mathematics,Combinatorics,Disjoint sets,Permutation,Regular polygon,Transversal (geometry),Tangent,Mathematics,Encoding (memory) | Journal |
Volume | Issue | ISSN |
28 | 1 | 0209-9683 |
Citations | PageRank | References |
7 | 0.56 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jacob E. Goodman | 1 | 277 | 136.42 |
| Richard Pollack | 2 | 912 | 203.75 |