Conference rusure::math

41.0. "N-clusters" by HARE::STAN () Thu Feb 23 1984 18:43

Newsgroups: net.math
Path: decwrl!decvax!harpo!seismo!hao!hplabs!menlo70!nsc!chongo
Subject: N Cluster problem - Easy to state/hard to solve?
Posted: Sat Feb 11 00:39:45 1984


The following problem is due to DBell and Chongo:

Definition - N Cluster
	N points on a regular 2D Lattice, no 3 co-linear, no 4 co-circular,
	an integral distance between each pair.

Or in another way:
	N points on a plane with integers as co-ordinates.  No 3 are in a
	line, and no 4 can be on a circle.  The distance between each pair
	of points is an integer.  A 5 cluster example is given below.

Problems:
	- Find a 6 cluster.
	- For all N, do N clusters exist?
	- For a given N, how many non-scaled N clusters exist?
	- Is there an N>2 cluster for which all clusters of higher order
	    contain it as a subset?
	- Can you always generate an N+1 cluster given a scaled N cluster?
	- For a given N, what is the smallest (or largest) unscaled N cluster?
	- Consider the more general problem by removing one or both of the
	    Lattice and the co-circular restrictions.

chongo <5 cluster: (0,0) (0,-153) (136,102) (-136,102) (224,207)> /\??/\

Newsgroups: net.math
Path: decwrl!decvax!harpo!seismo!uwvax!crystal!kalsow
Subject: Re: N-clusters
Posted: Mon Feb 20 09:06:41 1984

We define the SIZE of an N-cluster containing the origin to be
    the radius of the smallest disc centered at the origin that
    contains the N-cluster.

Here's what we found with 1.5 hours of 11/780:

    The 'smallest' 5-cluster:  (SIZE: 56)
    (0, 0) (56, 0) (-16, 30) (16, 30) (0, -33) 

    The 'smallest' 6-cluster:  (SIZE: 1275)
    (0, 0) (1155, 540) (546, -272) (132, -720) (960, -720) (546, 1120) 


                            Bryan Rosenburg   (bryan@uwisc)
                            Bill Kalsow       (kalsow@uwisc)