Complexity of point-to-planar convex set distance

In computer science, there are several equivalent ways to define a com-
putable compact set in $\R^k$. One of them is the so called “locally com-
putable compact set”, that is, being able to decide whether or not a given
ball intersects the set – this is often referred to as the “pixel information” of
the set because, loosely speaking, it allows us to know which pixels must be
coloured when drawing a picture of the set on a screen. It is not hard to see
that from the pixel information of a set one can compute the distance to a
given point, but the computational cost of doing so may be very different for
different sets.

In this talk we discuss the computational complexity of point-to-set dis-
tance restricted to planar convex bounded sets using a geometrical approach.
In particular we will show that in this case there is an algorithm to compute
this distance in polynomial time.

This is a joint work with M. Hoyrup.

Date: Aug 14, 2019 at 14:30:00 h
Venue: Sala 33, Av. República 701.
Speaker: Alonso Herrera
Affiliation: U. Andrés Bello.
Coordinator: Prof. José Verschae
More info at:
Event website

Posted on Aug 12, 2019 in AGCO, Seminars