KAIST Discrete Math Seminar

In shape matching, we are given two geometric objects and we compute their distance according to some geometric similarity measure. The Fréchet distance is a natural distance function for continuous shapes such as curves and surfaces, and is defined using reparameterizations of the shapes.

The discrete Fréchet distance is a variant of the Fréchet distance in which we only consider vertices of polygonal curves. In this talk, we consider the problem of computing the discrete Fréchet distance between two polygonal curves when their vertices are imprecise, and describe efficient algorithms for the problem.

The fractional weak discrepancy of a poset (partially ordered set) P, written wd(P), is the least k such that some satisfies f(y)-f(x)≤1 for and |f(y)-f(x)|≤k for x|y. Minimal forbidden subposets are often called obstructions. Shuchat, Shull, and Trenk determined the obstructions for the property wd(P)<1: the obstructions are 2+2 and 3+1. We determine the obstructions for the property wd(P)≤k when k is an integer. In this talk, the complete collection of the obstructions for wd(P)≤k for each k≥2 – which is an infinite set – will be discussed.

This is joint work with Douglas B. West.

A graph G on n vertices is pancyclic if it contains cycles of length t for all . We prove that for any fixed , the random graph G(n,p) with asymptotically almost surely has the following resilience property. If H is a subgraph of G with maximum degree at most then G-H is pancyclic. In fact, we prove a more general result which says that if for some integer then for any , asymptotically almost surely every subgraph of G(n,p) with minimum degree greater than contains cycles of length t for all . These results are tight in two ways. First, the condition on p essentially cannot be relaxed. Second, it is impossible to improve the constant 1/2 in the assumption for the minimum degree.

Joint work with Michael Krivelevich and Benny Sudakov