A fast 3D collision detection algorithm

I'm trying to work through the math here, and I don't understand why these two propositions are equivalent:

1) min_{x,y} |x-y|^2

   x ∈ A

   y ∈ B

2) = min_{x,y} d

   d ≥ |x-y|^2

   x ∈ A

   y ∈ B

What is 'd'? If d is much greater than |x-y|^2 at the actual (x, y) with minimal distance, and equal to |x-y|^2 at some other (x', y'), couldn't (2) yield a different, wrong solution? Is it implied that 'd' is a measure or something, such that it's somehow constrained or bounded to prevent this?

I can't read substack on my phone, so I can't see the article, but the correct statement that is closest to what you have written is just that d is any real number satisfying this inequality. We define a subset U of AxBxR by

U={(a,b,x):x>|a-b|^2}

and then were looking for the infimum of (the image of) U under the third coordinate function

d(a,b,x)=x

But why would d be much greater. The problem asks to minimise d, and so it cannot be greater than the smallest |x-y|^2.

This is the epigraph form of the problem. You try to find the point with the lowest height in the epigraph.

https://en.wikipedia.org/wiki/Epigraph_(mathematics)

I think you are missing that d, x, and y are variables that get optimized over. Any choice of d lower than the the solution to 1) is infeasible. Any d higher than the solution to 1) is suboptimal.

edit: I see now that the problem 2) is missing d in the subscript of optimization variables. I think this is a typo.

Ah, got it, thanks!!