Answers are grounded in this paper and cite their sources.
Let P be a set of points on the plane, and d(p, q) be the distance between a pair of points p, q in P. For a point p∈P and a subset S ⊂ P with |S|≥3, the 2-dispersion cost, denoted by cost2(p, S), of p with respect to S is the sum of (1) the distance from p to the nearest point in S{p} and (2) the distance from p to the second nearest point in S{p}. The 2-dispersion cost cost2(S) of S ⊂ P with |S|≥3 is minp∈S{cost2(p, S)}. Given a set P of n points and an integer k we wish to compute k point subset S of P with maximum cost2(S). In this paper we give a simple 1/({4√3}) approximation algorithm for the problem.
No takes yet. Share an insight, caveat, or question.
Amano et al. (2020) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: