4
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ If $S$ is a set of points in the plane, what does it mean for a distance to be larger than $S$? $\endgroup$ Aug 8, 2013 at 0:02
  • $\begingroup$ 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 $\endgroup$
    – Yemon Choi
    Aug 8, 2013 at 0:11
  • $\begingroup$ Sorry for my English. I have edited the question and now I hope it's clear. $\endgroup$ Aug 8, 2013 at 0:21

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you! I had never thought about this side of Borsuk's problem. That's really interesting. $\endgroup$ Aug 10, 2013 at 21:44
2
$\begingroup$

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 http://www.freeimagehosting.net/newuploads/mgfbd.png

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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