hide
Free keywords:
-
Abstract:
Let P be a set of n points in the plane. A crossing-free structure on P is a
straight-edge planar graph with vertex set in P. Examples of crossing-free
structures include triangulations of P, and spanning cycles of P, also known as
polygonalizations of P, among others. There has been a large amount of research
trying to bound the number of such structures. In particular, bounding the
number of triangulations spanned by P has received considerable attention. It
is currently known that every set of n points has at most O(30^n) and at least
(2.43^n) triangulations. However, much less is known about the algorithmic
problem of counting crossing-free structures of a given set P. For example, no
algorithm for counting triangulations is known that, on all instances, performs
faster than enumerating all triangulations. In this paper we develop a general
technique for computing the number of crossing-free structures of an input set
P. We apply the technique to obtain algorithms for computing the number of
triangulations and spanning cycles of P. The running time of our algorithms is
upper bounded by n^O(k), where k is the number of onion layers of P. In
particular, we show that our algorithm for counting triangulations is not
slower than O(3.1414^n). Given that there are several well-studied
configurations of points with at least (3.464^n) triangulations, and some even
with (8^n) triangulations, our algorithm is the first to asymptotically
outperform any enumeration algorithm for such instances. In fact, it is widely
believed that any set of n points must have at least (3.464^n) triangulations.
If this is true, then our algorithm is strictly sub-linear in the number of
triangulations counted. We also show that our techniques are general enough to
solve the restricted triangulation counting problem, which we prove to be
W[2]-hard in the parameter k. This implies a �no free lunch� result: In order
to be fixed-parameter tractable, our general algorithm must rely on additional
properties that are specific to the considered class of structures.
