Date:

Mon, 27/03/201711:00-13:00

Location:

Rothberg B220 (CS bldg)

Speaker: Micha Sharir (Tel Aviv University)

Title: Eliminating depth cycles for lines and triangles, with applications to bounding incidences

Abstract:

---------

The talk presents three related results.

We first consider the problem of eliminating all depth cycles in a set of n lines in 3-space.

For two lines l_1, l_2 in 3-space (in general position), we say that l_1 lies below l_2 if the

unique vertical line that meets both lines meets l_1 at a point below the point where it meets l_2.

This depth relationship typically has cycles, which can be eliminated if we cut the lines into

smaller pieces. A 25-year old problem asks for a sharp upper bound on the number of such cuts.

We show that this can be done with O(n^{3/2} polylog(n)) cuts, almost meeting the known worst-case

lower bound Omega(n^{3/2}).

The second topic extends the previous result to eliminating depth cycles in a set of pairwise

disjoint triangles in 3-space. (This is the "real" problem one would like to solve, motivated

by applications to computer graphics.) The depth relationship is defined in an analogous manner,

and cycles can be eliminated by cutting the triangles into simply-shaped pieces for which the

depth relationship is acyclic. A well known (albeit non-trivial) way of doing this is to use

a binary space partition, which produces quadratically many cuts (into triangular pieces).

We extend the cycle elimination result for lines to this setup, and show that all depth cycles

can be eliminated by cutting the triangles into O(n^{3/2+eps}) pieces, for any eps>0, where

each piece is a semialgebraic region of constant complexity (where this complexity depends on eps).

The extension is fairly involved, as it needs to use fairly sophisticated topological arguments

(unnecessary for the case of lines) to control the number of pieces.

The third topic is based on a straightforward, albeit technically demanding, extension of the

first result to eliminating cycles in a set of n algebraic arcs of constant degree in 3-space, with

a similar upper bound, close to n^{3/2}, on the number of required cuts. Combining this with a recent

idea of Ellenberg, Solymosi, and Zahl, we obtain new incidence bounds for points and arbitrary

fixed-degree algebraic curves in the plane.

All these developments are based on the polynomial partitioning technique of Guth and Katz, and

constitute a somewhat "unorthodox" application of this tool, which we hope will have follow-up

applications of a similar nature.

Based on joint works with Boris Aronov, Ed Miller, and Joshua Zahl.

Title: Eliminating depth cycles for lines and triangles, with applications to bounding incidences

Abstract:

---------

The talk presents three related results.

We first consider the problem of eliminating all depth cycles in a set of n lines in 3-space.

For two lines l_1, l_2 in 3-space (in general position), we say that l_1 lies below l_2 if the

unique vertical line that meets both lines meets l_1 at a point below the point where it meets l_2.

This depth relationship typically has cycles, which can be eliminated if we cut the lines into

smaller pieces. A 25-year old problem asks for a sharp upper bound on the number of such cuts.

We show that this can be done with O(n^{3/2} polylog(n)) cuts, almost meeting the known worst-case

lower bound Omega(n^{3/2}).

The second topic extends the previous result to eliminating depth cycles in a set of pairwise

disjoint triangles in 3-space. (This is the "real" problem one would like to solve, motivated

by applications to computer graphics.) The depth relationship is defined in an analogous manner,

and cycles can be eliminated by cutting the triangles into simply-shaped pieces for which the

depth relationship is acyclic. A well known (albeit non-trivial) way of doing this is to use

a binary space partition, which produces quadratically many cuts (into triangular pieces).

We extend the cycle elimination result for lines to this setup, and show that all depth cycles

can be eliminated by cutting the triangles into O(n^{3/2+eps}) pieces, for any eps>0, where

each piece is a semialgebraic region of constant complexity (where this complexity depends on eps).

The extension is fairly involved, as it needs to use fairly sophisticated topological arguments

(unnecessary for the case of lines) to control the number of pieces.

The third topic is based on a straightforward, albeit technically demanding, extension of the

first result to eliminating cycles in a set of n algebraic arcs of constant degree in 3-space, with

a similar upper bound, close to n^{3/2}, on the number of required cuts. Combining this with a recent

idea of Ellenberg, Solymosi, and Zahl, we obtain new incidence bounds for points and arbitrary

fixed-degree algebraic curves in the plane.

All these developments are based on the polynomial partitioning technique of Guth and Katz, and

constitute a somewhat "unorthodox" application of this tool, which we hope will have follow-up

applications of a similar nature.

Based on joint works with Boris Aronov, Ed Miller, and Joshua Zahl.