Multitriangulations, pseudotriangulations and primitive sorting networks

Details Multitriangulations, pseudotriangulations and primitive sorting networks Multitriangulations, pseudotriangulations and primitive sorting networks

2010-09-27

arxiv.org/abs/1009.5344v2

Mathematics

Combinatorics

60 pages, 40 figures; minor corrections and improvements of presentation

Scientific paper

10.1007/s00454-012-9408-6

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.

Affiliated with

Also associated with

No associations

Rating

Multitriangulations, pseudotriangulations and primitive sorting networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Multitriangulations, pseudotriangulations and primitive sorting networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multitriangulations, pseudotriangulations and primitive sorting networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-518556