Helly’s Theorem and Helly Property

helly

Helly’s theorem

Let X_1, X_2 \ldots X_n be a set of points in R^d. If the intersection of all possible d+1 of these sets are non empty then the whole intersection is non-empty also.

For example, let’s consider a set of paths P_1, P_2, \ldots P_n in R^1. Then if all couple of paths has a non-empty intersection then the intersection of all paths is also non-empty.

On the other hand, in R^2 let’s consider a set of unit circles C_1, C_2, \ldots C_n. Observe that even if all couple of circles are touching this does not imply that the intersection is not empty.

Every two circles intersect but the intersection of all circles are empty

But by Helly’s Theorem we know that if all triples of circles are intersect implies that the total intersection is not empty.

Helly’s Family and Helly Property

We say that a family of sets (for example set of circles in R^3) is a Helly Family of order k if k is the minimal number such that non-empty intersection of subsets of size k has a non-empty total intersection. The k-Helly property is the property of being a Helly family of order k. A 2-Helly family is also known as a Helly family and the 2-Helly property is also known as the Helly property.

Helly Property in Graph Thoery

It is possible to derive maximum clique algorithms for special graph classes like interval graphs or unit disk graphs using this property.

Comments are closed.