2
$\begingroup$

Can we place $14$ points in a regular hexagon of side $2$ such that the minimal distance between points is $>1$?

Background:

We can place $13$ points in a regular hexagon of side $2$ so that the minimal distance between $2$ points is $\frac{2}{\sqrt{3}}$. For this, divide the hexagon into $6$ equilateral triangles and consider the points: $6$ -- vertices of the hexagon, $6$ the center of the triangles, and $1$ the center of the hexagon, $13$ in total.

We can place $19$ points in the hexagon such that the minimal distance between them is $1$. For this, divide the hexagon into equilateral triangles of side $1$ and consider all the possible vertices, $19$ in number.

From this answer, whenever we take $20$ points in the hexagon, the minimal distance between them is $\le 1$.

From this answer, whenever we take $19$ points in the hexagon, the minimal distance between them is $\le 1$. ( I believe the result, not totally sure about the proof).

Connected results would be great too. Thanks for your interest!

$\endgroup$
6
$\begingroup$

Here are 15 points with minimal distance $1$ and all minimal distances marked.

enter image description here

Now, move the blue points towards the centre a bit (e.g., until they form a smaller equilateral triangle and with blue-blue distances equal to blue-red -- that is, with these distances $=3-\sqrt3=1.2679\ldots$). That allows you to move the green dots inwards as well, thereby making all distances slightly $>1$.

enter image description here

(Finally, drop one of the points in order to reach the desired number of $14$ points.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Excellent, very nice construction, thanks! $\endgroup$ – orangeskid Feb 29 at 7:04
  • $\begingroup$ Using the drawing in the other answer, places your triangle inscribed in the curved hexagon. Now we can use an inscribed rhombus instead and wiggle it a bit to get all sides $>1$, then apply your method to contract the midpoints, to get $16$ points instead. I would be very suprised if a pentagon with sides $>1$ fits inside the curved hexagon. $\endgroup$ – orangeskid Feb 29 at 7:47
  • $\begingroup$ I added a picture in my answer that is relevant. Your method requires having something in the curved center region. $\endgroup$ – orangeskid Feb 29 at 8:08
5
$\begingroup$

Can this way work? We can at most put 11 points on the side. The gray part means the area in which points will have <= 1 distance with those 11 points. So there will still be an acceptable area in the middle for the rest of 3 points. enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Great answer, very intuitive, thanks! $\endgroup$ – orangeskid Feb 29 at 6:59
  • $\begingroup$ Your curved hexagon + solution of Hagen shows how to get in fact $16$ points, $\endgroup$ – orangeskid Feb 29 at 7:50
  • 1
    $\begingroup$ See my answer and the remark comparing it to yours. I think that where you have 12, 13, 14, you could additionally fit a 15 and 16. $\endgroup$ – alex.jordan Feb 29 at 7:50
  • $\begingroup$ @orangeskid I don't see 16 ? $\endgroup$ – Hagen von Eitzen Feb 29 at 7:56
4
$\begingroup$

Iris had a nice idea to draw the allowed curved region.
enter image description here

Now we use @Hagen von Eitzen: method but instead of placing in the curved region a triangle, we place a quadrilateral with all sides $>1$. Wiggling a bit ( same method) gets us $16$ points all separated by more than $1$.
It turns out that we can place a pentagon with vertices in the curved region and all sides of length $>1$. The same method now gives us $17$ points in the hexagon with parwise distances $>1$.

enter image description here

Calculation that the top vertex of the regular pentagon is below the top arc: we have the height of the pentagon $=\frac{\sqrt{5 + 2 \sqrt{5}}}{2}\cdot 1$, so we need to check that $$2 \sqrt{3} - (1 +\frac{\sqrt{5 + 2 \sqrt{5}}}{2} + \frac{\sqrt{3}}{2})= 0.0592\ldots>0$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ There is such an amazing place in the middle part! How do you determine whether the pentagon will intersect the circle of point j, h, I, j after wiggling a bit? $\endgroup$ – Iris Feb 29 at 9:27
  • 2
    $\begingroup$ @Iris: First I used Geogebra and zoomed in to convince myself. Initially the regular pentagon has size $1$ and base the same as the small hexagon. With some properties of distance I check that the side vertices are in the curved region. The fact that the top point is inside should follow from a calculation. Now, I wiggle the pentagon vertically up,now strictly inside, now dilate a bit to make all sizes $>1$, now wiggle the midpoints of the original hexagon. (Hagen's method). But the curved region is yours really! Thanks! $\endgroup$ – orangeskid Feb 29 at 9:38
  • 1
    $\begingroup$ Your discovery let me understand I can learn more from answering others' questions.I really appreciate. $\endgroup$ – Iris Feb 29 at 9:55
  • 2
    $\begingroup$ Great! So the side-1 pentagon fit in with two vertices exactly at intersecting circles, the next two vertices in the free region (because a length 1 edge is rotated inwards, away from the possibly conflicting points), and by your calculation, the fifth vertex still fits in wit a bit of leeway - and "a bit of leeway" (in the right directions) is enough to move and enlarge all critical edges ... $\endgroup$ – Hagen von Eitzen Feb 29 at 10:35
  • 2
    $\begingroup$ To summarize: By this answer, $17$ points with distance $>1$ are possible; by one of the references in the question, $19$ points with distance $>1$ are impossible. The obvious question then is - what about $18$ points? $\endgroup$ – Hagen von Eitzen Feb 29 at 10:37
2
$\begingroup$

Here is a way to fit 16 points inside, such that the minimum distance is greater than $1$.

enter image description here

  1. Begin the construction with the regular pentagon in the middle.
  2. Construct the equilateral triangles below it.
  3. Construct a line parallel to the base line thus far, slightly below it.
  4. Extend the edges of the outer triangles to meet the line from the previous step.
  5. Construct the hexagon using the points found in the previous step. Declare this hexagon's edge to be 2 units, and it follows that all point-to-point distances so far are greater than 1.
  6. Construct $A'$ and $B'$ using reflection.
  7. Equilateral triangles for $R$ and $S$.
  8. There are lots of way to put in the last two points at the top. The illustration uses one last equilateral triangle.

Note that the points could all be shifted up a tiny bit, and then they would all fit even in the interior of the hexagon.

Take a look at @Iris's answer. I believe it is similar to this. Mine also has 11 points "around the edge". They could probably be distributed evenly like in @Iris's answer. @Iris put three points in the middle, but perhaps did not realize a pentagon could fit there too.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I used Iris curved hexagon + Hagen wiggling method to get $16$ points. The idea is that inside the curved hexagon we fit a quadrilateral with sides $>1$. I an not sure whether a pentagon with sides $>1$ would fit inside, if it did we would get $17$ points. $\endgroup$ – orangeskid Feb 29 at 7:55
  • $\begingroup$ @yes, you got $16$ points, now i understand, they were at min distance $1$ but strictly inside ( after a small vertical translate), then a small homothety makes all distances $>1$. Excellent, thank you! I see: the pentagon inside collapses the initial structure so the next points are strictly inside. How neat! $\endgroup$ – orangeskid Feb 29 at 10:18
  • $\begingroup$ Please check out the new construction in my answer that also features a pentagon. It manages $17$ points I think yours can also get $17$. $\endgroup$ – orangeskid Feb 29 at 10:23
1
$\begingroup$

Alternative solution:

Consider a regular hexagon of side $2$ given by the linear inequalities (denote by $H$): \begin{align} \pm \frac{x}{2} \pm \frac{y}{2\sqrt{3}} &\le 1, \\ \pm y &\le \sqrt{3}. \end{align} We need to find $(x_i, y_i) \in H, i = 1, 2, \cdots, 14$ such that $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} > 1$ for any $1\le i < j \le 14$.

Using Matlab global optimization solver, we find a feasible solution as follows: \begin{align} (299/739, \sqrt{3}),\\ (-53/345, 751/982),\\ (-411/577, \sqrt{3}),\\ (-243/185, 333/421),\\ (-2 + 109\sqrt{3}/2157, -109/719),\\ (-2 + 263\sqrt{3}/705, -263/235),\\ (-253/603, -\sqrt{3}), \\ (101/547, -236/301),\\ (87/112, -\sqrt{3}),\\ (2-261\sqrt{3}/895, -783/895),\\ (2-38\sqrt{3}/693, 38/231),\\ (2-266\sqrt{3}/705, 266/235),\\ (682/867, 137/862),\\ (-224/297, -66/373). \end{align} (Use Maple to check its feasibility)

It holds that $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} > 1.116$ for any $1\le i < j \le 14$.

Remarks: This numerical approach works for $n \le 17$. Anybody knows better global optimization solvers?

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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