Extremal configurations and levels in pseudoline arrangements Conference Paper uri icon


  • Abstract This paper studies a variety of problems involving certain types of extreme configurations in arrangements of (x-monotone) pseudo-lines. For example, we obtain a very simple proof of the bound O (nk 1/3) on the maximum complexity of the k-th level in an arrangement of n pseudo-lines, which becomes even simpler in the case of lines. We thus simplify considerably the previous proof by Tamaki and Tokuyama (and also simplify Dey's proof for lines). We also consider diamonds and anti-diamonds in (simple) pseudo-line arrangements, where a diamond (resp., an anti-diamond) is a pair u, v of vertices, so that u lies in the double wedge of v and vice versa (resp., neither u nor v lies in the other double wedge). We show that the maximum size of a diamond-free set of vertices in an arrangement of n pseudo-lines is 3n—6, by showing that the induced graph (where each vertex of the …

publication date

  • January 1, 2003