A couple of simple algorithms for k-dispersion

Abstract Given a set P of n points in $$\mathbb {R}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:math> , and a positive integer $$k \le n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> , the k -dispersion problem is that of selecting k of the given points so that the minimum inter-point distance among them is maximized (under Euclidean distances). Among others, we show the following: Given a set P of n points in the plane, and a positive integer $$k \ge 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , the k -dispersion problem can be solved by an algorithm running in $$O\left( n^{k-1} \log {n}\right) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mfenced> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mfenced> </mml:mrow> </mml:math> time. This extends an earlier result for $$k=3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> , due to Horiyama, Nakano, Saitoh, Suetsugu, Suzuki, Uehara, Uno, and Wasa [20] to arbitrary k . In particular, it improves on previous running times for small k . Given a set P of n points in $$\mathbb {R}^3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mn>3</mml:mn> </mml:msup> </mml:math> , and a positive integer $$k \ge 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , the k -dispersion problem can be solved by an algorithm running in $$ {\left\{ \begin{array}{ll} O\left( n^{k-1} \log {n}\right) \text {time}, &amp; \text {if } k \text { is even};\ O\left( n^{k-1} \log ^2{n}\right) \text {time}, &amp; \text {if } k \text { is odd}. \end{array}\right. } $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfenced> <mml:mrow> <mml:mtable> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mi>O</mml:mi> <mml:mfenced> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mfenced> <mml:mtext>time</mml:mtext> <mml:mo>,</mml:mo> </mml:mrow> </mml:mtd> <mml:mtd> <mml:mrow> <mml:mtext>if</mml:mtext> <mml:mspace/> <mml:mi>k</mml:mi> <mml:mspace/> <mml:mtext>is even</mml:mtext> <mml:mo>;</mml:mo> </mml:mrow> </mml:mtd> </mml:mtr> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mrow/> <mml:mi>O</mml:mi> <mml:mfenced>