Personal tools
You are here: Home CG seminar 2022 Hopcroft's Problem Revisited (or How to Shave a Log-Star)
« December 2021 »
December
SuMoTuWeThFrSa
1234
567891011
12131415161718
19202122232425
262728293031
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