Ernie and the Drill Test

Question

I dropped in to Ernie's place a while back and he asked me to stay and help calibrate his new Drilling Device. It was an impressive looking machine consisting of a large raygun-like thing mounted on an x-y translation table. An electronic eye was supported above the table, and to one side was a box with two buttons, one red and one blue.

Ernie explained that he was sick of drilling countless holes in sheets of steel manually, so he had built this tool to do the job automatically. "The extraordinarily accurate x-y table has precisely 1000 mm x 1000 mm of travel, so I can cut holes anywhere within an area of one square meter - accurate to the nearest micron. The drill uses an incredibly powerful laser to drill the holes so it takes absolutely no time at all to make the hole. The translation stage has enormously powerful, but restrained, drive motors so it can move the drill between any two locations in the one metre square area at a speed of precisely 1 m/s."

"But how does it know where to drill the holes?", I asked.

"Ahh", Ernie replied, "I felt that an analogue approach was more desirable than a digital one for this job, so you just mark where you want to put the holes on the steel sheet with these two special pens. You draw a circle with the red pen and that is where the drill puts the first hole, and you add a series of crosses with the blue pen to tell the drill where to put the rest of the holes. The electro-mechanical brain works out what path to follow and when to drill"

It felt like a typical Ernie invention - weirdly simple in some ways, but bizarrely complicated in other ways. "Tell me more?", I asked, "what do the two buttons do?". And Ernie explained that each button followed a very exact algorithm.

Red button: 
If a red circle exists:   
   Move the drill, in a straight line, from its current position to the centre of the red circle.

Blue Button:
Drill a hole.
While un-drilled blue crosses exist
   Move the drill, in a straight line, to the centre of the nearest blue cross,
   Drill a hole.

Ernie asked me to mark a plate so we could test the system. I marked the first plate with exactly one red circle and five blue crosses (the plate was a bit oversize so there was plenty of room to mark all the drill-points within the central 1000 mm x 1000 mm square that the drill could reach.). We mounted the plate and Ernie pressed the Red button - the drill moved until it was exactly over the red cross. Then he pressed the Blue button and simultaneously started a stop-watch. There were 6 bright flashes (and a little more flying molten steel than I had expected) as the drill made the holes in the plate. At the exact moment the sixth hole was made, Ernie stopped the watch.

"Hmmm", he exclaimed, and then very carefully measured the positions of the holes in the plate with a ruler. "You seem, quite by chance of course, to have chosen hole positions that maximize the time required for the drill to complete the Blue algorithm for six holes!".

This only happened a few weeks ago ago but Ernie never told me exactly how long it took the Blue algorithm to drill the six holes, or where (exactly) in the steel in the sheet I drew the red circle. Can you help me?

If that is all to easy, I plan to visit Ernie around Christmas and would love to play with his head by "quite by chance" marking out a seven hole plate which maximizes the Blue algorithm time, so knowing where to mark the red circle and six blue crosses would be useful. Ernie only uses his second-best stop-watch and ruler for this kind of job, so positions accurate to the nearest micron, and times to the nearest microsecond should be sufficient.

Answer 1

Starting with @Lopsy's answer for 6 holes, I was able to get a larger value. Here's how I went about it:

First, I assume that if two blue crosses are equidistant from the drill, then the drill can choose either, and I should assume that the smaller total path is the total distance.

With 2 holes, the holes must go in opposite corners.
$(0, 0), (1, 1)$

With 3 holes, the holes go in any 3 corners, starting with the one adjacent to the other two.
$(0, 0), (1, 0), (0, 1)$

With 4 holes, the holes go in 3 corners and on the diagonal, making sure the diagonal length is less than 1. Start with corner adjacent to the other two.
$(0, 0), (\sqrt2/2, \sqrt2/2), (1, 0), (0, 1)$

With 5 holes it gets interesting. Using the existing holes, the obvious place for the 5th hole is the empty corner. However, once this is done, the center hole can be moved to give a longer distance. It maximizes at $(\sqrt3/2, 0.5)$.
$(0, 0), (\sqrt3/2, 0.5), (1, 1), (1, 0), (0, 1)$

For the 6th hole, there is now an equilateral triangle with vertices at $(0, 0), (0, 1), (\sqrt3/2, 0.5)$. The sixth hole goes in the center of this triangle, at $(\sqrt3/6, 0.5)$

Tweaking the 2 non-corner points and starting in the center of the triangle gives the following 6 points in the order they would be drilled:
$(0.288674, 0.499999), (0, 0), (0.866024, 0.500001), (1, 1), (0, 1), (1, 0)$
The total distance is 4.509199 meters.

For the 7th dot, there's a large space in the upper half of the area with nothing, so getting it as far from $(0.255674, 0.499999)$ as possible while still making it the closest dot gives a point of $(0.500000, 0.955388)$. With this as the new starting point you have the following 7 points in the order they would be drilled:
$(0.500000, 0.955388), (0.288674, 0.499999), (0, 0), (0.866024, 0.500001), (1, 1), (0, 1), (1, 0)$
The total distance is 5.011189 meters.

While looking for 6 dots, I tried various placements. For example, I started with the full area and tried points at every 0.1 meter point, then picked the best ones and scaled down to 0.01 meter and so on. So I'm fairly confident in my answer.

For 7 dots, I assumed the positioning of the first 6 dots wouldn't change, found a spot for the 7th dot, then tested the values to make sure they were at least a local maximum (meaning that there might be a longer distance, but there wouldn't be one using the same approximate positioning). So I think my answer is correct, but I wouldn't be surprised if a drastic re-positioning of all 3 points turned out a larger distance.

Answer 2

Here are my punts for six and seven holes. The lengths are:

Six holes: $2+\sqrt 2+2\sqrt{2-\sqrt{3}}=4.449...$ meters
Seven holes: $2+ \sqrt 2+3\sqrt{2-\sqrt{3}}=4.967...$ meters

First off, six holes:

If this is a unit square, then the non-corner holes are at $A=(\frac 12, \frac {\sqrt{3}}{2})$ and $B=(\frac {\sqrt{3}}{2}, \frac 12)$. Many distances are equal, so adjust the hole positions by a very tiny amount so that the drill path is the red path shown.

Now seven holes. Just add one more hole, symmetrically, at $C=(\frac 12, 1-\frac {\sqrt 3}{2})$, and then change $B$ to the red hole.

Again, adjust the hole positions by a very tiny amount so that the drill path is the red path shown.

For reference, if we add an eighth point to complete the symmetry (shown below), then all the red distances and all the blue distances are equal.

Answer 3

I find it useful to start with the last point and add priors, at each step visualizing a bounding area. It's usually helpful to consider at least 2 points ahead, because to cross between two existing points requires taking a shorter hop to the vicinity of the mid-point between them, but is worthwhile on the next hop. For seven points I get (excluding fudge factors to force choices):

¼√3,¼
0,½
0,1
½√3,½
1,0
1,1
0,0

total distance 4.93185

For eight points use the same sequence with the addition of ¼√3,¾ at the beginning, giving

¼√3,¾
¼√3,¼
0,½
0,1
½√3,½
1,0
1,1
0,0

total distance 5.43185

A ninth point would go where the bisector of (1,1)~(¼√3,¾) intersects (0,1)~(1,1), approximately 1,0.666 .

Answer 4

As a bit of an update. Having seen a recent post on this question I asked Ernie if he knew the optimal solutions for six or more holes. Ernie muttered a bit about optimality but then drew the following diagram for me. He spent some time pointing out the regular tetrahedrons and the four axes of symmetry in the 9 hole solution and said that he thought that "That one, at least, is probaly optimal"

Approximate path lengths are 4.50920, 5,01119, 5.49467, 5.85079, 6.16915,6.48949, and 6.80002 for 6, 7, 8, 9, 10, 11, and 12 holes respectively. I pointed at the enpty corner of the diagram and asked about 13 holes. But he just said "Dont you have anything better to do?"