3
\$\begingroup\$

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
\$\endgroup\$
7
  • 1
    \$\begingroup\$ 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? \$\endgroup\$
    – RubenVerg
    Commented Jun 7 at 13:49
  • 4
    \$\begingroup\$ 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? \$\endgroup\$
    – Neil
    Commented Jun 7 at 14:09
  • \$\begingroup\$ @RubenVerg Assume that the length of both are the same. \$\endgroup\$
    – bigyihsuan
    Commented Jun 7 at 15:29
  • \$\begingroup\$ @Neil Minimum distance is maximal. \$\endgroup\$
    – bigyihsuan
    Commented Jun 7 at 15:29
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – quarague
    Commented Jun 8 at 8:57

7 Answers 7

2
\$\begingroup\$

Charcoal, 25 bytes, O(n²)

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

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

≔Eθ⌊EηΣEλX⁻ν§ιξ²η

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ The code size is just the 2nd criterion. What's the time complexity? \$\endgroup\$
    – Arnauld
    Commented Jun 7 at 14:27
  • \$\begingroup\$ 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. \$\endgroup\$
    – Graham
    Commented Jun 7 at 14:42
  • \$\begingroup\$ 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. \$\endgroup\$
    – akamayu
    Commented Jun 10 at 3:20
  • \$\begingroup\$ @akamayu Thanks. So from that do I conclude the overall time complexity is O(n2). \$\endgroup\$
    – Graham
    Commented Jun 10 at 18:30
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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().

screenshot

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) } 
)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.