**Abstract:**

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.

Venue: Sala 33, Av. República 701.

Speaker: Alonso Herrera

Affiliation: U. Andrés Bello.

Coordinator: Prof. José Verschae