Journal: Discrete & Computational Geometry

Abbreviation

Discrete comput. geom.

Publisher

Springer

Journal Volumes

ISSN

0179-5376
1432-0444

Description

Filters

Reset filters

Search Results

Publications1 - 10 of 53
  • Connectivity of Triangulation Flip Graphs in the Plane
    Item type: Journal Article
    Wagner, Uli; Welzl, Emo (2022)
    Discrete & Computational Geometry
    Given a finite point set P in general position in the plane, a full triangulation of P is a maximal straight-line embedded plane graph on P. A partial triangulation of P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge (called edge flip), removes a non-extreme point of degree 3, or adds a point in P \ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The edge flip graph is defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early seventies that these graphs are connected. The goal of this paper is to investigate the structure of these graphs, with emphasis on their vertex connectivity. For sets P of n points in the plane in general position, we show that the edge flip graph is inverted right perpendicularn/2 - 2inverted left perpendicular-vertex connected, and the bistellar flip graph is (n - 3)-vertex connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull), where (n - 3)-vertex connectivity has been known since the late eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky and Balinski's Theorem. For the edge flip-graph, we additionally show that the vertex connectivity is at least as large as (and hence equal to) the minimum degree (i.e., the minimum number of flippable edges in any full triangulation), provided that n is large enough. Our methods also yield several other results: (i) The edge flip graph can be covered by graphs of polytopes of dimension inverted right pependicularn/2 - 2inverted left pependicular (products of associahedra) and the bistellar flip graph can be covered by graphs of polytopes of dimension n - 3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n - 3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations of a point set are regular iff the partial order of partial subdivisions has height n - 3. (iv) There are arbitrarily large sets P with non-regular partial triangulations and such that every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular triangulations.
  • Complete Enumeration of Small Realizable Oriented Matroids
    Item type: Journal Article
    Fukuda, K.; Miyata, H.; Moriyama, S. (2013)
    Discrete & Computational Geometry
  • Random Sampling with Removal
    Item type: Journal Article
    Clarkson, Kenneth L.; Gärtner, Bernd; Lengler, Johannes; et al. (2020)
    Discrete & Computational Geometry
    We study randomized algorithms for constrained optimization, in abstract frameworks that include, in strictly increasing generality: convex programming; LP-type problems; violator spaces; and a setting we introduce, consistent spaces. Such algorithms typically involve a step of finding the optimal solution for a random sample of the constraints. They exploit the condition that, in finite dimension δ, this sample optimum violates a provably small expected fraction of the non-sampled constraints, with the fraction decreasing in the sample size r. We extend such algorithms by considering the technique of removal, where a fixed number k of constraints are removed from the sample according to a fixed rule, with the goal of improving the solution quality. This may have the effect of increasing the number of violated non-sampled constraints. We study this increase, and bound it in a variety of general settings. This work is motivated by, and extends, results on removal as proposed for chance-constrained optimization. For many relevant values of r, δ, and k, we prove matching upper and lower bounds for the expected number of constraints violated by a random sample, after the removal of k constraints. For a large range of values of k, the new upper bounds improve the previously best bounds for LP-type problems, which moreover had only been known in special cases, and not in the generality we consider. Moreover, we show that our results extend from finite to infinite spaces, for chance-constrained optimization. (© Springer 2020)
  • Directed trees in a string, real polynomials with triple roots, and chain mails
    Item type: Journal Article
    Kozlov, Dmitry N. (2004)
    Discrete & Computational Geometry
    This paper starts with an observation that two infinite series of simplicial complexes, which a priori do not seem to have anything to do with each other, have the same homotopy type. One series consists of the complexes of directed forests on a double directed string, while the other one consists of Shapiro–Welker models for the spaces of hyperbolic polynomials with a triple root. We explain this coincidence in the more general context by finding an explicit homotopy equivalence between complexes of directed forests on a double directed tree, and doubly disconnecting complexes of a tree.
  • Counting Triangulations and Other Crossing-Free Structures via Onion Layers
    Item type: Journal Article
    Alvarez, Victor; Bringmann, Karl; Curticapean, Radu; et al. (2015)
    Discrete & Computational Geometry
  • Extendability of Continuous Maps Is Undecidable
    Item type: Journal Article
    Čadek, Martin; Krčál, Marek; Matoušek, Jiří; et al. (2014)
    Discrete & Computational Geometry
  • A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon
    Item type: Journal Article
    Ahn, Hee-Kap; Barba, Luis; Bose, Prosenjit; et al. (2016)
    Discrete & Computational Geometry
  • On Gromov's Method of Selecting Heavily Covered Points
    Item type: Journal Article
    Matoušek, Jiří; Wagner, Uli (2014)
    Discrete & Computational Geometry
  • Deep Cliques in Point Sets
    Item type: Journal Article
    Langerman, Stefan; Mydlarz, Marcelo; Welzl, Emo (2023)
    Discrete & Computational Geometry
  • k-Sets in Four Dimensions
    Item type: Journal Article
    Matoušek, Jiří; Sharir, Micha; Smorodinsky, Shakhar; et al. (2006)
    Discrete & Computational Geometry
Publications1 - 10 of 53