Speaker: Gabriel Nivasch (Ariel)

Title: On the zone of a circle in an arrangement of lines

Abstract:
---------
Edelsbrunner et al. (1992) showed that the zone of a convex curve (like 
a circle or a parabola) in an arrangement of lines has complexity O(n alpha(n)), 
where alpha is the inverse Ackermann function, by translating the sequence of 
edges of the zone into a Davenport-Schinzel sequence S of order 3. Whether the 
complexity is only linear in n is a longstanding open problem.

Here we show that, for the case of a parabola, S avoids not only "ababa" but 
another pattern u as well. Hence, if Ex({"ababa", u, u^R}, n) could be shown 
to be O(n), that would settle the problem for a parabola (and almost certainly 
also for a circle).

See arXiv:1503.3462