Center for Global Studies

Back to Listing

Theory Seminar: David Zheng, Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees

Event Type
Seminar/Symposium
Sponsor
Chandra Chekuri
Location
https://illinois.zoom.us/j/85054031332?pwd=d1hRNS9wTlVFRmtpTzZmQkxld1YzZz09
Virtual
wifi event
Date
Dec 6, 2021   10:00 am  
Views
20
Originating Calendar
Computer Science Speakers Calendar

Zoom info:

https://illinois.zoom.us/j/85054031332?pwd=d1hRNS9wTlVFRmtpTzZmQkxld1YzZz09

Meeting ID: 850 5403 1332

Passcode: theorycs

 

 

Title: Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees

Link: https://arxiv.org/abs/2111.03744

 

Abstract: We revisit Hopcroft's problem and related fundamental problems about geometric range searching. Given $n$ points and $n$ lines in the plane, we show how to count the number of point-line incidence pairs or the number of point-above-line pairs in $O(n^{4/3})$ time, which matches the conjectured lower bound and improves the best previous time bound of $n^{4/3}2^{O(\log^*n)}$ obtained almost 30 years ago by Matou\v{s}ek.

We describe two interesting and different ways to achieve the result: the first is randomized and uses a new 2D version of fractional cascading for arrangements of lines; the second is deterministic and uses decision trees in a manner inspired by the sorting technique of Fredman (1976).  The second approach extends to any constant dimension.

 

Many consequences follow from these new ideas: for example, we obtain an $O(n^{4/3})$-time algorithm for line segment intersection counting in the plane, $O(n^{4/3})$-time randomized algorithms for bichromatic closest pair and Euclidean minimum spanning tree in three or four dimensions, and a randomized data structure for halfplane range counting in the plane with $O(n^{4/3})$ preprocessing time and space and $O(n^{1/3})$ query time.

 

Joint work with Timothy Chan.

link for robots only