3.64M

Asish_Mukhopadhyay (1)

1.

Asish Mukhopadhyay
Around the Sylvester–Gallai theorem
Dedicated to one of the hardest problems from the 2026 ICPC NWERC quarterfinals.

2.

A career in algorithms
1977
M.Sc. in Applied Mathematics
1984
Ph.D. in Applied Mathematics
1986–98
University of Calcutta
Indian Institute of Science
Computational
geometry
Graph algorithms
Bioinformatics
Faculty
IIT Kanpur
1997 / 2007 / 2012
1999–
Faculty
University of Windsor, Canada
Finding an ordinary line
O(n log n)

3.

The ordinary line problem
Exactly two points
Not all collinear:
an ordinary line exists.
How many exist?
How do we find one?
Brute force
Random sampling
Mukhopadhyay–Greene

4.

A proof becomes an algorithm
“Just look at the Sylvester–Gallai proof.”
Choose a pair Q, R
Choose P off QR
P
Minimise positive distance
d(P, QR)
n points × O(n²) lines
Q
R
O(n³)
Still expensive

5.

Random sampling
Pick two points uniformly
Try again if the line is not ordinary
Θ(n²) ordinary lines
E[trials] = O(1)
Solved in O(1)?

6.

The hidden cost
O(n)
One check: a scan of all n points
n − 1 on a line, one off
Böröczky: ellipse + line
n − 1 ordinary lines
n/2 ordinary lines
p = Θ(1/n)
Green–Tao, 2013
E[time] = Θ(n²)
Even: ≥ n/2
For sufficiently large n. Both bounds are sharp.
Odd: ≥ 3⌊n/4⌋

7.

Mukhopadhyay–Greene
1 Supporting line ℓ₀
S
2 Sort rays around O
One point on a ray?
Return its line with O.
R
Q
P
U
3 Adjacent rays, extreme points
T
ℓ₀
O
Polar sort
4 Closest intersection A
A
min |OA|
O(n log n)
Candidate scan
O(n)

8.

Questions
01
02
03
An n × n grid
No convex hull?
Two or three points
How many ordinary lines?
Find a supporting line
What is the minimum?
B
A
O
Θ(n⁴)
4 × 4 example: 48
Lowest, then leftmost O
External angle bisector
n−1
For n ≥ 5. Same near-pencil.

9.

Thank you
Questions?
English     Русский Rules