From: "Andreas Björklund" <oldmoose@algonet.se>
Subject: Re: "airport" problem
Date: Wed, 5 Jan 2000 08:20:41 +0100
Newsgroups: sci.math
Summary: [missing]

>Let S be the unit square [0,1]x[0,1].  Take any n points (x1, y1), (x2,
>y2),...,(xn, yn) in S.  Find an algorithm that will compute:
>
>d = sup{min distance from (x, y) to some (xi, yi) | (x, y) in S}
>

This is exactly the largest enclosed circle problem, i.e. what is the radius
of the largest circle whose origin lies within [0,1]x[0,1] and doesn't
contain any of the n points. A well-studied problem, see e.g
Preparata,Shamos -- Computational Geometry. I bet Voronoi diagrams are part
of the story...

>Does using the taxicab distance or the max{|x-xi|, |y-yi|} distance
>simplify the problem?

In some sense, yes. Trying to fit a square seem "easier" than placing a
circle, but I believe the computational costs are approximately the same.

Regards,
Andreas