Name
Abstract | ||
|---|---|---|
We show that a set of n points in the plane has at most O(10.05n) perfect matchings with crossing-free straight-line embedding. The expected number of perfect crossing-free matchings of a set of n points drawn i.i.d. from an arbitrary distribution in the plane is at most O(9.24n).Several related bounds are derived: (a) The number of all (not necessarily perfect) crossing-free matchings is at most O(10.43n). (b) The number of left-right perfect crossing-free matchings (where the points are designated as left or as right endpoints of the matching edges) is at most O(5.38n). (c) The number of perfect crossing-free matchings across a line (where all the matching edges must cross a fixed halving line of the set) is at most 4n.These bounds are employed to infer that a set of n points in the plane has at most O(86.81n) crossing-free spanning cycles (simple polygonizations), and at most O(12.24n) crossing-free partitions (partitions of the point set, so that the convex hulls of the individual parts are pairwise disjoint).
|
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1109557.1109652 | SODA: Symposium on Discrete Algorithms |
Keywords | DocType | Volume |
simple polygonizations,red-blue perfect crossing-free matchings,perfect matchings,expected number,crossing-free matchings,crossing-free straight-line embedding,matching edge,blue point,perfect crossing-free matchings,crossing- free matchings,counting,crossing-free partition,n point,point set,left-right perfect crossing-free matchings,crossing-free partitions.,crossing-free geometric graphs,graph,face,polyhedron,facet,polytope,linear inequalities,vertex,cycle | Conference | 36 |
Issue | ISBN | Citations |
3 | 0-89871-605-5 | 48 |
PageRank | References | Authors |
3.27 | 23 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Micha Sharir | 1 | 8405 | 1183.84 |
| E. Welzl | 2 | 3311 | 552.52 |