Personal tools
You are here: Home CG seminar 2022 Hopcroft's Problem Revisited (or How to Shave a Log-Star)
« August 2022 »
August
SuMoTuWeThFrSa
123456
78910111213
14151617181920
21222324252627
28293031
Log in


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)

underline

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).
Document Actions