From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few Vertices
- PDF / 623,278 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 15 Downloads / 194 Views
From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few Vertices Alexander Pilz1 · Emo Welzl2 · Manuel Wettstein2 Received: 7 January 2019 / Revised: 28 August 2019 / Accepted: 13 October 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract A set P = H ∪ {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 crossingfree geometric graphs on such a set P, it suffices to know the frequency vector of P. While there are roughly 2n distinct order types that correspond to wheel sets, the number of frequency vectors is only about 2n/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 Rd for any fixed d. 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 Rd in time O(n max{ω,k−2} ) where ω ≈ 2.373, even though the asymptotic number of facets may be as large as n k .
Dedicated to the memory of Ricky Pollack. Editor in Charge: János Pach Alexander Pilz [email protected] Emo Welzl [email protected] Manuel Wettstein [email protected] 1
Institute of Software Technology, Graz University of Technology, Graz, Austria
2
Department of Computer Science, ETH Zürich, Zurich, Switzerland
123
Discrete & Computational Geometry
Keywords Geometric graphs · Order types · Frequency vectors · Embracing triangles · Simplicial depth · Polytopes Mathematics Subject Classification 05A19 · 05C30 · 52C99
1 Introduction Computing the number of non-crossing straight-line drawings of certain graph classes (triangulations, spanning trees, etc.) on a planar point set is a well-known problem in computational and discrete geometry. While for point sets in convex position many of these numbers have simple closed formulas, it seems difficult to compute them efficiently for a given general point set, or to provide tight upper and lower bounds. In this paper, we provide means for solving these problems for a special class of point sets that we call wheel sets. Conowheel Sets Let P = H ∪ {w} be a set of n + 1 points in the plane. Unless stated otherwise, P is assumed to be in general position (i.e., no three points on a common line) and the points in H are assumed to be extreme (i.e
Data Loading...
