Multitriangulations, pseudotriangulations and primitive sorting networks

DOI10.1007/S00454-012-9408-6zbMATH Open1247.52012arXiv1009.5344OpenAlexW1784352241MaRDI QIDQ443914FDOQ443914

Authors: Vincent Pilaud, Michel Pocchiola 

Publication date: 13 August 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We study the set of all pseudoline arrangements with contact points which cover a given support. We define a natural notion of flip between these arrangements and study the graph of these flips. In particular, we provide an enumeration algorithm for arrangements with a given support, based on the properties of certain greedy pseudoline arrangements and on their connection with sorting networks. Both the running time per arrangement and the working space of our algorithm are polynomial. As the motivation for this work, we provide in this paper a new interpretation of both pseudotriangulations and multitriangulations in terms of pseudoline arrangements on specific supports. This interpretation explains their common properties and leads to a natural definition of multipseudotriangulations, which generalizes both. We study elementary properties of multipseudotriangulations and compare them to iterations of pseudotriangulations.

Full work available at URL: https://arxiv.org/abs/1009.5344

Recommendations

• The brick polytope of a sorting network
• The brick polytope of a sorting network
• Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
• Enumerating pseudo-triangulations in the plane
• scientific article; zbMATH DE number 1182898

zbMATH Keywords

flippseudoline arrangementenumeration algorithmsorting networkmultitriangulationpseudotriangulation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Cites Work

• Title not available (Why is that?)
• Oriented Matroids
• Maximal fillings of Moon polyominoes, simplicial complexes, and Schubert polynomials
• Arrangements of double pseudolines
• Title not available (Why is that?)
• Subword complexes in Coxeter groups.
• Brick polytopes of spherical subword complexes and generalized associahedra
• On the number of pseudo-triangulations of certain point sets
• The brick polytope of a sorting network
• A new perspective on \(k\)-triangulations
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Realizations of the associahedron and cyclohedron
• Multitriangulations as complexes of star polygons
• Generalized triangulations and diagonal-free subsets of stack polyominoes
• Pseudo-triangulations -- a survey
• Title not available (Why is that?)
• Convexity minimizes pseudo-triangulations
• Axioms and hulls
• Computing pseudotriangulations via branched coverings
• Planar minimally rigid graphs and pseudo-triangulations
• Acute triangulations of polygons
• A Turán-type theorem on chords of a convex polygon
• A generalization of diagonal flips in a convex polygon
• Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs
• Topologically sweeping visibility complexes via pseudotriangulations
• On line arrangements in the hyperbolic plane
• THE VISIBILITY COMPLEX
• Title not available (Why is that?)
• Enumerating pseudo-triangulations in the plane
• Sorting by means of swappings
• Tight degree bounds for pseudo-triangulations of points
• Transforming pseudo-triangulations
• Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
• Entering and leaving \(j\)-facets
• \(2kn-\binom{2k+1}{2}\). A note on extremal combinatorics of cyclic split systems

Cited In (26)

• The brick polytope of a sorting network
• Fan realizations of type \(A\) subword complexes and multi-associahedra of rank 3
• Fan realizations for some 2-associahedra
• Brick manifolds and toric varieties of brick polytopes
• Pipe dream complexes and triangulations of root polytopes belong together
• Cambrian acyclic domains: counting \(c\)-singletons
• The brick polytope of a sorting network
• Associahedra via spines
• The \(\nu \)-Tamari lattice via \(\nu \)-trees, \( \nu \)-bracket vectors, and subword complexes
• Title not available (Why is that?)
• Hopf dreams
• Subword complexes via triangulations of root polytopes
• Brick polytopes, lattice quotients, and Hopf algebras
• Hopf dreams and diagonal harmonics
• A Hopf algebra of subword complexes
• Brick polytopes of spherical subword complexes and generalized associahedra
• Denominator vectors and compatibility degrees in cluster algebras of finite type
• Subword complexes, cluster complexes, and generalized multi-associahedra
• A Hopf algebra of subword complexes (Extended abstract)
• \(\nu\)-Tamari lattices via subword complexes
• Cluster algebras of type \(D\): pseudotriangulations approach
• Toric matrix Schubert varieties and their polytopes
• The diameter of type \(D\) associahedra and the non-leaving-face property
• Celebrating Loday's associahedron
• Vertex barycenter of generalized associahedra
• Computing pseudotriangulations via branched coverings

This page was built for publication: Multitriangulations, pseudotriangulations and primitive sorting networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q443914)