discrete geometrylinear programming
There are $k$ points placed inside a polygon and I am interested in finding a point inside the polygon (not necessarily on its boundary) who's minimum distance to any of the $k$ points is maximized.
I guess one way of attacking the problem would be through a linear program, but this looks a bit messy. Does anybody have any other ideas for an algorithm?
[Edit: I had originally posted a proof that finding the minimum value was NP-hard; in the comments below, Brendan McKay pointed out how to convert that into a proof that finding the maximum value is NP-hard, which was the question asked by the original poster. I have edited this to include a complete answer to the original question.]
Let's refer to the operation of replacing two values $b,c$ in a multiset by the single value $|b-c|$ as a "contraction"; the original poster asks if it is possible to find an ordering of repeated contractions that maximizes the final value.
In this post, we begin by asking if we can find the order with the minimum possible value. Specifically, we try to determine whether the minimum value is zero or greater than zero. We will show that deciding this question is NP-complete. (We need to make it into a decision problem ("is it equal to zero?") rather than a minimization problem ("what's the smallest value?") to phrase it in terms of NP-completeness.) We then show how to convert this result into a statement about the maximum rather than minimum value.
Also, to Johan Wastlund's comment above, a slight modification of the construction gives an $O(2^{n-2})$ lower on the maximum number of distinct values that can be produced (which I'll outline at the bottom).
Determining if the minimum value is zero is clearly in NP-- we can simply (non-deterministically) guess the correct pattern of steps to produce zero. Showing that it is NP-complete takes a little more effort. We will show this by a reduction from the partition problem.
Take an instance of the partition problem with inputs $x_1,...,x_n$. We are trying to find a subset $S\subseteq \{1,...,n\}$ such that $\sum_{i\in S}x_i=\sum_{i\not\in S}x_i$.
Set $M_1=M_2=2\sum_i x_i$. Consider the multiset $\{M_1,M_2,x_1,...,x_n\}$. Let $f(x,y)=|x-y|$. Since we have taken $M_1$ to be so large, it follows that
$$f(\cdots(f(f(M_1,x_{i_1}),x_{i_2}),\cdots),x_{i_k})=M_1-\sum_{j=1}^k x_{i_j}$$
and similarly for $M_2$.
Claim: if there exists a subset $S$ that partitions the integers $x_1,...,x_n$, then the minimum value attained by repeated contractions is zero.
Proof: Assume that such an $S$ exists. Then we can apply $f$ to $M_1$ and the elements of $S$ to get
$$M_1-\sum_{i\in S}x_i$$
and similarly with $M_2$ and the complement of $S$ to get
$$M_1-\sum_{i\not\in S}x_i$$
As our last step, we can subtract these and get zero. Since the output value is non-negative, then the minimum value is zero.
Claim: if an ordering of repeated contractions produces a final value of zero, then we can produce a partition from this ordering in polynomial time.
Proof: The computation of the final value attained by the repeated contraction corresponds to the evaluation of $f$ on a binary tree with the leaf nodes labeled by $x_1,...,x_n$. As pointed out in the comments above, we can "squash" this tree (in $O(n)$ time) and show that the output is equal to the sum $\sum_i \pm x_i$. If we let $S$ correspond to the $x_i$ with a positive index, we have constructed the desired partition.
We have shown above that determining whether the smallest value is zero is NP-complete. We now show that this implies the same complexity for the maximum.
Specifically, take $x_1,...,x_n$ and observe that the maximum possible value that can be achieved by repeated contraction is $\max_i x_i$. We now ask the question: is the maximum final value achieved by repeated contraction equal to $\max_i x_i$, or is it strictly smaller?
We will show that deciding this question is NP-complete. It is clearly in NP, since we can exhibit an ordering of contractions that achieves the maximum, if such an ordering exists.
To show that it is NP-complete, we will reduce from the problem of determining if there is an ordering of repeated contractions that equals zero.
Take the multiset $A=\{x_1,...,x_n\}$ and consider a new element $M=1+\sum_i x_i$. Let $B=A\cup \{M\}$. Note that $M$ is the unique maximum over $B$.
We first show that if the maximum final value for the repeated contraction of $B$ is $M$, then the minimum repeated contraction of $A$ is 0. If there exists a repeated contraction with final sum $M$, then any contraction that involves $M$ must be of the form $f(M,0)$ (otherwise the final sum would be strictly less than $M$) and vice versa. Suppose that we replace $M$ by 0; the same pattern of contractions will now produce a final value of 0. Therefore, we have produced a pattern of contractions on $A\cup \{0\}$ that gives a final value of zero.
In the other direction, we show that if the minimum final value for the repeated contraction of $A$ is 0, then the maximum value for $B$ is $M$. Suppose that the minimum repeated contraction of $A$ is 0. Then consider the identical pattern of contractions on $B$, which will leave us with $M$ and 0; the last contraction will produce $|M-0|=M$
Therefore, we can determine if the minimum final value of $A$ (which was arbitrary) is zero if an only if we can determine if the maximum final value of $B$ is $M$.
Therefore, the problem of determining if the maximum final value of a repeated contraction is equal to the maximum of the original set is NP-complete.
Johan Wastlund asked, as a function of $n$, what the maximum number of distinct values can be produced by applying $f$ in all possible combinations? He suggested it might be $2^{n-2}$. The construction above can be modified to show that there are at least this many possibilities.
Let $x_i=2^i$, for $i=1,...,n-2$. Let $M_1=2^{n-1}$ and let $M_2=2^n$. Since
$$M_z>\sum_{i=1}^{n-2}$$
(for $z=1,2$) then we still have $$f(\cdots(f(f(M_z,x_{i_1}),x_{i_2}),\cdots),x_{i_k})=M_z-\sum_{j=1}^k x_{i_j}$$
Let $S$ be the subset of indices subtracted from $M_1$. Then we can construct the sum $$f(M_1-\sum_{i\in S}^k x_{i},M_2-\sum_{i\not\in S}^k x_{i})= M_2-M_1+(\sum_{i\in S}^k x_{i})-(\sum_{i\not\in S}^k x_{i})$$
This sum assumes a distinct value for each subset $S$ of $\{1,...,n-2\}$, so there are at least $2^{n-2}$ distinct values.
Perhaps it will help to investigate the medial axis of a polygon. It was discussed in this earlier MO question, Retraction of a Riemannian manifold with boundary to its cut locus. The junctions of the medial axis are points that are far from the boundary, centers of disks touching the boundary at three or more points—local maxima, to quote from Wlodek's comment. The medial axis can be computed for polygons with holes as well:
You may also find papers that focus directly on the largest incircle of a polygon, e.g., "An Efficient Algorithm to Calculate the Center of the Biggest Inscribed Circle in an Irregular Polygon" (arXiv link).
Best Answer
I may be misunderstanding your question, but could it(?) be rephrased as:
If this is a correct interpretation, let $S$ be the set of your $k$ points. Compute the Voronoi diagram of $S$, and intersect it with the polygon $P$, clipping all portions of the diagram exterior to $P$. Then your optimal center lies either at an interior Voronoi vertex, or at a vertex of $P$, or where a Voronoi edge crosses the boundary of $P$. You could check each such point.
The above solution assumes "distance" is Euclidean distance. But it is now clear from the OP's comment below that he is measuring distance by the shortest path within the polygon. And so the relevant object is the geodesic Voronoi diagram, just as he says:
(Image from this paper.)