Personal tools
You are here: Home CG seminar Fall 2017 New bounds and relations for some basic geometric problems
« July 2017 »
July
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
3031
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