# Find the most isolated point

Given two non-empty sets of points $$\P,T = \{(x,y)\ |\ x,y \in \mathbb{Z} \}\$$, find the point $$\p \in P\$$ such that it is the "most isolated" from all points in $$\T\$$. The "most isolated" point is defined as the point that maximizes the minimum distance to all points in a given set.

If multiple points are "most isolated", you must deterministically pick one of them. If no points are "most isolated", you must deterministically pick any point from $$\P\$$.

## Scoring Criteria

Your score is your average asymptotic time complexity (if the complexity depends on the length of $$\P\$$ and $$\T\$$, assume the lengths are the same). If multiple answers have the same time complexity, your code size in bytes is the tie-breaker. Lowest score wins!

## Worked Example

Consider $$\P=\{(1,2),(3,4),(5,6)\}\$$ and $$\T=\{(2,6),(7,1),(7,5)\}\$$. The distance of each point in $$\P\$$ to each point in $$\T\$$ is

# dict is of structure {p: {t: distance(p,t)}}
{(1, 2): {(2, 6): 4.123105625617661,
(7, 1): 6.082762530298219,
(7, 5): 6.708203932499369},
(3, 4): {(2, 6): 2.23606797749979,
(7, 1): 5.0,
(7, 5): 4.123105625617661},
(5, 6): {(2, 6): 3.0,
(7, 1): 5.385164807134504,
(7, 5): 2.23606797749979}}


In this example, the point $$\p \in P\$$ that is most isolated is the point $$\(1,2)\$$, since its distances are maximal to each point in $$\T\$$.

## Test Cases

# P, T -> output
[(1,2),(3,4),(5,6)], [(2,6),(7,1),(7,5)]
-> (1,2)
[(0,0)], [(0,0)]
-> (0,0)          # P and T are same point
[(0,0),(1,0)], [(0,0)]
-> (1,0)          # P and T contain the same point
[(1,0),(0,1)], [(0,0)]
-> (1,0) or (0,1) # multiple points are most isolated
[(123,456)], [(1,2),(3,4),(5,6)]
-> (123,456)      # P only contains 1 point
[(6,0),(6,4),(5,-3),(4,1),(6,3)], [(3,3)]
-> (5,-3)         # T only contains 1 point
[(1,1),(-1,-1)], [(2,2),(-2,-2)]
-> (1,1) or (-1,-1) # multiple points do not maximize distance from all points

• asymptotic time complexity here depends on two variables (length of $P$ and length of $T$), how do e.g. $O(p \log t)$ and $O(t \log p)$ compare, i.e. which solution wins? Commented Jun 7 at 13:49
• When you say maximises the distance to all points, do you mean that the minimum distance is maximal or that the sum of all distances is maximal or something else?
– Neil
Commented Jun 7 at 14:09
• @RubenVerg Assume that the length of both are the same. Commented Jun 7 at 15:29
• @Neil Minimum distance is maximal. Commented Jun 7 at 15:29
• Do you want average time complexity (for some probability distribution for the location of the points) or worst case time complexity? If the size of P and T is large I could see an algorithm that first makes an educated guess for most isolated and then only checks against that to be better than O(n^2) on average or most of the time but I don't think one can beat that as a worst case scenario. Commented Jun 8 at 8:57

# Charcoal, 25 bytes, O(n²)

≔Ｅθ⌊ＥηΣＥλＸ⁻ν§ιξ²η⭆¹§θ⌕η⌈η


Try it online! Link is to verbose version of code. Explanation:

≔Ｅθ⌊ＥηΣＥλＸ⁻ν§ιξ²η


For each point in P, calculate the squared distance to all points in T and take the minimum.

⭆¹§θ⌕η⌈η


Output the point in P that has the maximum minimum squared distance.

# K (ngn/k), $$\O(N^2)\$$, 22 bytes

A function that takes $$\P\$$ and $$\T\$$ as its first, and second argument, respectively.

{x.*>&/'+.'i*i:x-\:+y}
x-\:+y     1. coordinate diff between (p,t) in PxT
+.'i*i            2. squared distance between (p,t) in PxT
&/'                  3. minimal distance to all t in T for each p in P
*>                     4. index of the most isolated p in P
x.                       5. the most isolated p in P


Part 1,2,3 all use $$\O(N^2)\$$, part 4 uses $$\O(N\log N)\$$ and part 5 is $$\O(1)\$$. Therefore the overall time complexity is $$\O(N^2)\$$.

Try it online!

# APL+WIN, 26 bytes

Prompts for T then P as nested vectors of points:

P[↑⍒(+/¨((P←⎕)∘.-⎕)*2)*.5]


Try it online! Thanks to Dyalog Classic

• The code size is just the 2nd criterion. What's the time complexity? Commented Jun 7 at 14:27
• No idea. I do not know how APL implements its functions and operators such as grade down and outer product. Perhaps an APL expert can chime in with the answer. Commented Jun 7 at 14:42
• Not an APL expert here, but I think grade down is $O(n\log n)$ as indexing after grade forms a sort, which is $\Omega(n\log n)$. Outer product uses $O(n^2\cdot T)$ time since it performs an operation of complexity $O(T)$ between $O(n^2)$ pairs of elements. Commented Jun 10 at 3:20
• @akamayu Thanks. So from that do I conclude the overall time complexity is O(n2). Commented Jun 10 at 18:30

# JavaScript (ES7), $$\\mathcal{O}(n^2)\$$, 90 bytes

Expects (P)(T).

P=>T=>P.map(m=a=>(v=Math.min(...T.map(b=>(g=n=>(a[n]-b[n])**2)(0)+g(1))))<m||(m=v,o=a))&&o


Try it online!

# Python, $$\\mathcal{O}(n^2)\$$, 72 bytes

lambda P,T:max(P,key=lambda p:min((p[0]-X)**2+(p[1]-Y)**2 for X,Y in T))


Using math.dist requires import math, which amounts to the same number of bytes.

Attempt This Online!

# vemf, 13 bytes, O(n²)

Boring quadratic solution as a function that takes two lists of vectors. Could maybe be shorter with complex numbers?

├╛│╘│-╧¢ñ>@╓@
╛      ñ       ' Minimum for each pair in P,
│╘            ' For each pair at T
│-╧¢        ' distance of the difference
>@     ' Index of maximum
├          ╓@   ' Find at T


# Google Sheets, $$\O(n^2+)\$$, 109 bytes

let(d,map(x,y,lambda(x,y,min(map(z,t,lambda(z,t,sumsq(z-x,t-y)))))),index({x,y},+sort(sequence(rows(d)),d,)))


This is a named function rather than a formula. To implement it as a named function, paste the code in Data > Named functions. Points P are passed as the parameters x, y and points T are passed as z, t where each parameter is an array. To implement the function in a formula, wrap it in lambda().

Uses the same $$\O(n^2)\$$ approach as others, plus sort() to find the maximum.

Ungolfed:

=let(
Px, tocol(A2:A11, 1),
Py, tocol(B2:B11, 1),
Tx, tocol(C2:C11, 1),
Ty, tocol(D2:D11, 1),
minDistanceSquares, map(Px, Py, lambda(x, y,
min(
map(Tx, Ty, lambda(z, t,
sumsq(z - x, t - y)
))
)
)),
maxIndex, single(sort(
sequence(rows(minDistanceSquares)),
minDistanceSquares,
false
)),
maxDistance, sqrt(index(minDistanceSquares, maxIndex)),
{ maxDistance, maxIndex, index({ Px, Py }, maxIndex) }
)