A set P = H \cup \{w\} of n+1 points in general position in the plane is called a wheel set if all points but w are extreme. We show that for the purpose of counting crossing-free geometric graphs on  P, it suffices to know the so-calledfrequency vector of P. While there are roughly 2^n distinct order types that correspond to wheel sets, the number of frequency vectors is only about 2^{n/2}. We give simple formulas in terms of the frequency vector for the number of crossing-free spanning cycles, matchings, w-embracing triangles , and many more. Based on these formulas , the corresponding numbers of graphs can be computed efficiently.  Also in higher dimensions, wheel sets turn out to be a suitable model to approach the problem of computing the simplicial depth of a point ~ w in a set ~ H, i.e., the number of simplices spanned by~H that contain~w. While the concept of frequency vectors does not generalize easily, we show how to apply similar methods in higher dimensions . The result is an O(n^{d-1}) time algorithm for computing the simplicial depth of a point w in a set H of n d-dimensional points, improving on the previously best bound of O(n^d\log n). Configurations equivalent to wheel sets have already been used by Perles for counting the faces of high-dimensional polytopes with few vertices via the Gale dual. Based on that we can compute the number of facets of the convex hull of n=d+k points in general position in \mathbb{R}^d in time O(n^{\max\{\omega,k-2\}}) where \omega \approx 2.373, even though the asymptotic number of facets may be as large as n^k.
A set P = H \cup \{w\} of n+1 points in general position in the plane is called a wheel set if all points but w are extreme. We show that for the purpose of counting crossing-free geometric graphs on such a set P, it suffices to know the frequency vector of P. While there are roughly 2^n distinct order types that correspond to wheel sets, the number of frequency vectors is only about 2^{n/2}. We give simple formulas in terms of the frequency vector for the number of crossing-free spanning cycles, matchings, triangulations , and many more. Based on that , the corresponding numbers of graphs can be computed efficiently. In particular, we rediscover an already known formula for w-embracing triangles spanned by H. Also in higher dimensions, wheel sets turn out to be a suitable model to approach the problem of computing the simplicial depth of a point w in a set H, i.e., the number of w-embracing simplices. While our previous arguments in the plane do not generalize easily, we show how to use similar ideas in \mathbb{R . The result is an O(n^{d-1}) time algorithm for computing the simplicial depth of a point w in a set H of n points, improving on the previously best bound of O(n^d\log n). Based on our result about simplicial depth, we can compute the number of facets of the convex hull of n=d+k points in general position in \mathbb{R}^d in time O(n^{\max\{\omega,k-2\}}) where \omega \approx 2.373, even though the asymptotic number of facets may be as large as n^k.
R
wheel set
wheel set
A
such a set
D
so-called
R
frequency vector
frequency vector
R
w-embracing triangles
triangulations
R
these formulas
that
A
In particular, we rediscover an already known formula for w-embracing triangles spanned by H.
R
simplicial depth
simplicial depth
D
~
D
~
R
simplices spanned by~H that contain~w. While the concept of frequency vectors does
w-embracing simplices. While our previous arguments in the plane do
R
apply similar methods in higher dimensions
use similar ideas in \mathbb{R
D
d-dimensional
R
Configurations equivalent to wheel sets have already been used by Perles for counting the faces of high-dimensional polytopes with few vertices via the Gale dual. Based on that
Based on our result about simplicial depth,