Forgot your password?
Hopcroft's Problem Revisited (or How to Shave a Log-Star)
Wednesday, November 17th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)
Timothy Chan, UIUC
Abstract:
In this talk, I will describe new algorithms to find incidences between n
points and n lines in 2D in O(n^{4/3}) time, improving Matousek's previous result
from 30 years ago by a 2^{O(log^*n)} factor. The new techniques have applications
to numerous other range-searching-related problems (in 2D and higher), allowing
us to remove extraneous factors from many known theoretical time bounds.
Joint work with Da Wei Zheng (to appear in SODA'22).
