MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a 2-dimensional Borsuk's theorem:

Every bounded set $S$ in the plane can be partitioned into three parts with diameter smaller than the diameter of $S$.

I wonder if there are any results on variations of this problem which consider the following questions:

  • partitioning a finite plane set $S$ into parts with the minimum of the distances between its different points, larger than the minimum of the distances between different points of $S$;

  • partitioning a finite plane set $S$ into parts with minimum of the distances between its different points, larger than the minimum of the distances between different points of $S$, and/or with diameter, smaller than the diameter of $S$;

  • maybe other questions, connected with extremal characteristics of finite plane sets, other than diameter?

share|cite|improve this question
If $S$ is a set of points in the plane, what does it mean for a distance to be larger than $S$? – Gerry Myerson Aug 8 '13 at 0:02
Since edits were made to the English in the original post I thought I might as well join in. However, like @GerryMyerson I am confused as to what your first question is asking for – Yemon Choi Aug 8 '13 at 0:11
Sorry for my English. I have edited the question and now I hope it's clear. – Andrew Ryzhikov Aug 8 '13 at 0:21

The first question essentially asks what is the maximum chromatic number of the minimum distance graph of a finite set of points in the plane.

Let $S$ be a planar point set and let $m$ be the minimum distance between two points from $S$. The minimum distance graph $G$ of $S$ is a graph with vertex set $S$ and with edges connecting pairs of points $x,y$ such that $|x-y|=m$.

The problem is briefly discussed in P. Brass, W. Moser and J. Pach: Research problems in discrete geometry, in section 5.9 Chromatic number of unit distance graphs. It is observed that $G$ has chromatic number at most $4$, as $G$ is $3$-degenerate. Indeed, for every subset $T$ of $S$, every vertex of the convex hull of $T$ has degree at most $3$ in $G[T]$.

It is also easy to find an example of a point set $S$ where $3$ colors are not enough:

a minimum distance graph with chromatic number 4

See also G. Csizmadia, On the Independence Number of Minimum Distance Graphs for a related problem of finding large independent sets in $G$.

share|cite|improve this answer

I wonder if this satisfies the multiple criteria of what you seek...?

Johann Hagauera, Günter Rote. "Three-clustering of points in the plane." Computational Geometry Theory and Applications. Volume 8, Issue 2, July 1997, Pages 87–95. (Elsevier link)

Abstract. Given $n$ points in the plane, we partition them into three classes such that the maximum distance between two points in the same class is minimized. The algorithm takes $O(n^2\log^2 n)$ time.

This paper is lated cited for applications to clustering, e.g., Tetsuo Asano's paper, "Effective Use of Geometric Properties for Clustering."

share|cite|improve this answer
Thank you! I had never thought about this side of Borsuk's problem. That's really interesting. – Andrew Ryzhikov Aug 10 '13 at 21:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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