8
$\begingroup$

You have the same plugging task as in Find a straight tunnel , but now the problem requires a bit more imagination:

Bob has a field, which is a regular polygon with $N$ sides and perimeter $P$. There is a tunnel, which is just under the surface, but invisible - unless you dig. It is known that the tunnel goes under the field (at least touches it at one point), it is straight and infinitely long (in both directions).
Bob wants to find the tunnel. To do this he has a plow and can dig along some lines with it. If Bob plows and crosses the tunnel he will find it. Bob doesn't want to plow too much so he first figured a strategy out, which guarantees to find the tunnel by plowing at most $L$ meters.
What can be the smallest $k = L/P$ ratio, given $N$ can be any number from 3 to $\infty$?
Bob is allowed to plow only inside of his field. He can take the plow out of the ground and move it over the ground without plowing.

Important to note that now you can plow only inside and you can chose the field, which is best for you (i mean to chose $N$).

I tried extreme cases:
$N=\infty$ - it is circle and the best path is along the perimeter, so $k_{min}=1$.
$N=3$ - it is triangle, I belive the best case is a path along medians, then $k_{min}=1/\sqrt{3} \approx 0.5774$.
The best case should be somewhere inbetween.

Improve this question
$\endgroup$
9
  • $\begingroup$ @Oray, I will recheck my 0.5701 result, but are you sure this theory was talkingabout L/P, not something else? $\endgroup$
    – klm123
    Dec 29, 2016 at 20:20
  • $\begingroup$ It seems that for N=3 you have 2/3 in worst case - assuming the tunnel touches a corner. What is the strategy that guarantees the value you derived? $\endgroup$
    – Moti
    Dec 30, 2016 at 5:09
  • $\begingroup$ @Moti, "path along medians". 3/sqrt(3) is 2/3 of the all medians in the triangle. $\endgroup$
    – klm123
    Dec 30, 2016 at 7:35
  • $\begingroup$ I see now. Was this proved? So why not extend it to other cases? $\endgroup$
    – Moti
    Dec 30, 2016 at 17:45
  • $\begingroup$ For N greater than 5 it will be (N-1)/N (will check for 5 and 4) $\endgroup$
    – Moti
    Dec 30, 2016 at 20:04

3 Answers 3

Reset to default
4
$\begingroup$

This seems a little tricky to prove...

I hope the attached image explains my optimisation for the first n-sided polygon. I'll try to explain step by step.

First, n=3 is the exception and the best route is the path along the medians. Consider the case where n>3:

Begin with one vertex labelled (1). Trace the perimeter to the next vertex(V). Keep tracing to the next vertex until you find a vertex whereby (1),(V), and (V+1) forms an acute triangle. This allows you to drop an altitude from vertex(V+1) onto the line (1)-(V). From then on, repeat the same process for every vertex henceforth.

For the case of a square, we trace out the perimeter until the 3rd vertex, whereby it is more "economical" to drop the altitude to the line (1)-(3) than to trace out the next side. This shape will fully cover any possible tunnel going through the shape.

Let's take n=9 as another example. We can trace out four sides (or 5 vertices) until we see that the next vertex (6) would allow us to drop the altitude to line (1)-(5). Then, we repeat for every subsequent vertex that follows.

This is more economical than the naive solution of tracing out the entire parameter for each shape. I don't have a mathematically rigorous proof that these are the minimum cases for how much we need to plough, and hope the images can intuitively present that it may be the optimum solution.

Ultimately, this appears to give the minimum case that N=3 is the lowest L/P ratio. N=4 gives a L/p ratio of roughly 0.677, and the ratio slowly increases as n increases until we reach the limit of a circle, whereby L/P=1.enter image description here

Improve this answer
$\endgroup$
4
  • $\begingroup$ good job for big N's! I didn't know this solution. But for square and pentagon, at least, you can do better with other strategy. $\endgroup$
    – klm123
    Jan 2, 2017 at 18:12
  • $\begingroup$ @klm123 The two solutions for the square I considered were either making an "X" that crosses the centre of square (this gives plough length of $2\sqrt 2$) versus the solution I propose which is $2+\frac{\sqrt 2}{2}$, which is the smallest value I could find. Or am I incorrect and there is yet another solution for the square I haven't considered? My other guess would likely then be an angled "H" shape at 30deg...but I calculated it as $1+\frac{3}{\sqrt 3}$ which is still higher than the above. $\endgroup$
    – skyeriding
    Jan 2, 2017 at 18:29
  • $\begingroup$ for N=4 you can do at least 0.660 $\endgroup$
    – klm123
    Jan 2, 2017 at 22:19
  • $\begingroup$ @skyeriding For n=4, instead of drawing a perimeter between 123, treat it as an irregular n=3. I'm showing this as approx. 0.6597. Similar optimizations may be possible for the perimeters on your higher n. $\endgroup$
    – dmitch
    Jan 4, 2017 at 17:56
2
$\begingroup$

(Not a complete answer - total hypothesis, without mathematical backing or final calculation, but I believe it's correct)

We can't dig outside of the polygon. Therefore, in order to account for cases where the tunnel goes touches a corner of the polygon, our digging map must include all corners of the polygon.

If we dig a network that connects all the corners of the polygon, it's easy to see that we ensure we'll be able to find any tunnel that passes THROUGH the polygon (a tunnel passing through the polygon will have at least a vertex on either side, and our network of digging connects those vertices, therefore our network intersects the tunnel).

Now, the optimal network for joining points is actually quite obscure. I remember the solution (the network should consist of digging straights that intersect at 120 degrees only), but a 2 minute google search didn't give me a mathematical calculation nor an easy way to generally generate such a network. However, check out https://www.unige.ch/~gander/Preprints/BDM56-GanderE.pdf which should give you a general idea of the point I'm trying to convey.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The thing is - we don't Have to connect all corners. Most probably the best solution won't do it. $\endgroup$
    – klm123
    Jan 2, 2017 at 7:04
0
$\begingroup$

The ratio (N-1)/N is for N>4. For 3, 4 go through the center from vertices N times. For 5 and up go through N-1 edges.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Actually the (N-1)/N is true for N>5 $\endgroup$
    – Moti
    Dec 31, 2016 at 5:12
  • $\begingroup$ I don't understand what you are talking about. N=3.( N-1)/N= 2/3. 0.5774<2/3. This is not optimal already for N=3. $\endgroup$
    – klm123
    Dec 31, 2016 at 7:28
  • $\begingroup$ But for N>5 (N-1)/N looks like very probable optimum indeed. $\endgroup$
    – klm123
    Dec 31, 2016 at 7:40
  • $\begingroup$ For N = 5 (and if i am correctly interpreting what you're saying for the others) you can shorten at least one of the 'legs' while still being a solution. $\endgroup$
    – DrunkWolf
    Dec 31, 2016 at 18:12

Your Answer

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

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