Personal tools
You are here: Home CG seminar Fall 2017 New bounds and relations for some basic geometric problems
« March 2021 »
March
SuMoTuWeThFrSa
123456
78910111213
14151617181920
21222324252627
28293031
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