2
$\begingroup$

Suppose I am given a finite metric space as a distance matrix. What is the complexity of determining whether this metric space is hyperconvex?

Definition: A metric space is said to be hyperconvex if it is convex, and its closed balls have the (binary) Helly property. That is, if any family of closed balls intersects pairwise, then the entire family intersects.

I did some Googling, but so far have only found results about the theoretical properties of such spaces, not on matters related to computation.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Finite metric spaces with more than two points cannot be hyperconvex, because they cannot be convex. Just take the two closest points in the metric space. There are no points between them. Therefore, the space is not convex.

Improve this answer
$\endgroup$
1
  • $\begingroup$ doh! thanks for the sanity check... i guess a more sensible question would be whether balls satisfy the helly property, since that is sufficiently general $\endgroup$
    – pyridoxal_trigeminus
    Commented Sep 8, 2023 at 18:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .