# Problems similar to Borsuk’s Theorem in the plane

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?

-
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:

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

-

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."

-
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