References for largest empty circle voronoi diagrams

Question

I need some reference in order to get this idea I have in mind:

Given the largest empty circle problem, I want to determinate where to put new malls

My problem: If I have a map with divided in two by a sea, my voronoi diagram goes through the points without taking in count the geographic limit (i.e. if someone lives in the left side of the map, that person would not want to cross the sea to go to the mall)

Is there possibility or references to deal with this?

By the way I read Fortune's algorithm before

Answer 1

It seems to me you would like to put constraints on the position of the center C of your largest empty circle (LEC).

The abstract of: TOUSSAINT, Godfried T. Computing largest empty circles with location constraints. International journal of computer & information sciences, 1983, 12.5: 347-358, says:

In particular, it is shown that if the center of C is constrained to lie in an arbitrary convex n-gon, an O(n log n) algorithm can still be obtained.

Also: CHEW, L. Paul; DRYSDALE, Scot. Finding largest empty circles with location constraints. 1986. says:

We also improve on an algorithm given by Toussaint for computing the LEC when the center is constrained to lie within an arbitrary simple polygon.