Personal tools
You are here: Home CG seminar Fall 2017 New bounds and relations for some basic geometric problems
« January 2021 »
January
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
31
Log in


Forgot your password?
 

New bounds and relations for some basic geometric problems

Wednesday, November 16th, 2016, 16:10

Schreiber 309


underline

New bounds and relations for some basic geometric problems

Omer Gold, TAU

Abstract:

I will give an overview on recent conditional lower bounds for some basic (geometric) problems in P, then proceed with our recent upper bounds for these problems. Particularly, 3SUM, Fréchet Distance, Dynamic Time Warping, Geometric Edit Distance, Dominance Products, and high-dimensional Closest Pair problems. I will review the results and touch some of the techniques used to obtain them.

I will finish with our ongoing work towards breaking the quadratic barrier of some archetypal geometric problems, such as testing whether there are three collinear points in a set of n points in the plane.
(All works are joint with Micha Sharir.)
 
Document Actions