Name
Abstract | ||
|---|---|---|
Let $$P$$P be a set of $$n$$n points in the plane. A crossing-free structure on $$P$$P is a straight-edge plane graph with vertex set $$P$$P. Examples of crossing-free structures include triangulations and spanning cycles, also known as polygonalizations. In recent years, there has been a large amount of research trying to bound the number of such structures; in particular, bounding the number of (crossing-free) triangulations spanned by $$P$$P has received considerable attention. It is currently known that every set of $$n$$n points has at most O$$(30^{n})$$(30n) and at least $$\\Omega (2.43^{n})$$Ω(2.43n) triangulations. However, much less is known about the algorithmic problem of counting crossing-free structures of a given set $$P$$P. In this paper, we develop a general technique for computing the number of crossing-free structures of an input set $$P$$P. We apply the technique to obtain algorithms for computing the number of triangulations, matchings, and spanning cycles of $$P$$P. The running time of our algorithms is upper-bounded by $$n^{\\mathrm{O}(k)}$$nO(k), where $$k$$k is the number of onion layers of $$P$$P. In particular, for $$k = \\hbox {O}(1)$$k=O(1) our algorithms run in polynomial time. Additionally, we show that our algorithm for counting triangulations in the worst case over all $$k$$k takes time O$$^{*}(3.1414^{n})$$¿(3.1414n). [In the notations $$\\Omega ^{*}(\\cdot ), \\hbox {O}^{*}(\\cdot )$$Ω¿(·),O¿(·), and $$\\Theta ^{*}(\\cdot )$$¿¿(·), we neglect polynomial terms and we just present the dominating exponential term.] Given that there are several well-studied configurations of points with at least $$\\Omega (3.47^{n})$$Ω(3.47n) triangulations, and some even with $$\\Omega (8.65^{n})$$Ω(8.65n) triangulations, our algorithm asymptotically outperforms any enumeration algorithm for such instances. We also show that our techniques are general enough to solve the Restricted-Triangulation-Counting-Problem, which we prove to be $$W[2]$$W[2]-hard in the parameter $$k$$k. This implies that in order to be fixed-parameter tractable, our general algorithm must rely on additional properties that are specific to the considered class of crossing-free structures. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00454-015-9672-3 | Discrete & Computational Geometry |
Keywords | DocType | Volume |
Triangulations,Crossing-free structures,Algorithmic geometry,Counting algorithms,Matchings,Spanning cycles,Spanning trees | Journal | 53 |
Issue | ISSN | Citations |
4 | 0179-5376 | 1 |
PageRank | References | Authors |
0.35 | 28 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Victor Alvarez | 1 | 25 | 2.90 |
| Karl Bringmann | 2 | 427 | 30.13 |
| Radu Curticapean | 3 | 70 | 8.75 |
| Saurabh Ray | 4 | 228 | 24.28 |