Lost in a Cave - applying graph theory to cave exploration

Amy

New member
There was a thread about this on the US forum a while back. I CBA to find it though. I'm pretty sure it's legit. It makes sense....

(says the nerd who took graduate level graph theory back in college... >_> )
 

barrabus

New member
Martin Laverty said:
I don't think this is a joke, but I await some interesting Amazon reviews.

[quote author=Mr C.J. Binding's review]
The best thing I've bought in recent times and already it's saved my life twice (perhaps a bit melodramatic but things could have panned out so much worse); my copy is a bit dishevelled from use and a waterproof, or laminated, cover would be a good move for future print runs. I always take this book with me on my caving trips - it's a winning combination... go caving without a care in the world until you start to get tired, thirsty and hungry and then "hey presto!" whip out the book and apply graph theory to resolve the hopeless state of lost-ness which has crept upon you while aimlessly wandering around the subterranean mazes of complexity which abound in this part of the UK. I used to leave a call out so people knew where I was heading (just in case I was late coming home) but now I just slip Dick's magnus opus into my oversuit and press on without a care in the world.

It would be great if someone could write graph theory into an android phone app `cos that would help me figure out my route to safety and victory a bit quicker. One for the future, eh, Mr. Breisch.

I do occasionally worry that I might forget to take it with me but my group members always remind me before we descend into the yawning dark abyss by saying "Sir, have you got that book on navigation with you?". It's an absolute god send and a winner. Wouldn't go caving without it.[/quote]

He's got to be joking....!
 

bograt

Active member
Do android phone apps actually work when you have mislaid yourself in "the subterranean mazes of complexity" far from "safety and victory"?
 

TheBitterEnd

Well-known member
It's character building and educational - learn maths or die alone in a cold dark cave having eaten your mates ...
 

menacer

Active member
bograt said:
Do android phone apps actually work when you have mislaid yourself in "the subterranean mazes of complexity" far from "safety and victory"?

Absolutely.
Worked perfectly the pdf version of the felix trombe through trip, france and hoya san Felipe in Tenerife.
 

kay

Well-known member
The truth is always more boring:

"Here, we deal with a problem of guaranteed search on graphs ?with a radius of capture?...the main features of the guaranteed search in general can be studied from the article (Breisch, 1967) by speleologist Richard Breisch. Breisch considered the following problem. A person is lost in a cave, which is in total darkness, and wandering aimlessly. We are looking for an efficient way for rescue party to search the lost person: what is the minimum number of searchers required to explore a cave so that it is impossible to miss finding the victim if he is in the cave. ...
Now, let the cave be represented by the finite connected graph G so that the rooms are described by vertices and the passages ? by edges. We may assume that G is embedded in IR3 so that its vertices are points in IR3 and its edges are represented by closed line segments which intersect only at vertices of G. The searchers must proceed according to a predetermined plan which will find the lost man even if he was that sort of victim who knows the searcher?s every move, is arbitrarily fast and invisible for rescuers, and tries to avoid meeting "

from:
Graph Searching Games with a Radius of Capture ⋆ Tatiana V. Abramovskaya and Nikolai N. Petrov, presented at the Fourth International Conference Game Theory and Management June 28-30, 2010, St. Petersburg, Russia

It can be very hard for mathematicians trying to make their book stand out from all the other books on the subject ...
 

Amy

New member
Is it bad that this made sense to me? Graph theory was my favourite math course in undergrad, and the professor was the best professor I ever had. Lucked out and had him for three courses. Graph Theory was the one class that almost got the math department the rare female recruit - but I hated calculus so simply did a minor in applied math instead to avoid multivariable calculus.

...I really want this book.

Do you happen to have the full text of that presentation, Kay? I'd love to read it. I dont have access to the university library anymore =(

kay said:
"Here, we deal with a problem of guaranteed search on graphs ?with a radius of capture?...the main features of the guaranteed search in general can be studied from the article (Breisch, 1967) by speleologist Richard Breisch. Breisch considered the following problem. A person is lost in a cave, which is in total darkness, and wandering aimlessly. We are looking for an efficient way for rescue party to search the lost person: what is the minimum number of searchers required to explore a cave so that it is impossible to miss finding the victim if he is in the cave. ...
Now, let the cave be represented by the finite connected graph G so that the rooms are described by vertices and the passages ? by edges. We may assume that G is embedded in IR3 so that its vertices are points in IR3 and its edges are represented by closed line segments which intersect only at vertices of G. The searchers must proceed according to a predetermined plan which will find the lost man even if he was that sort of victim who knows the searcher?s every move, is arbitrarily fast and invisible for rescuers, and tries to avoid meeting "

from:
Graph Searching Games with a Radius of Capture ⋆ Tatiana V. Abramovskaya and Nikolai N. Petrov, presented at the Fourth International Conference Game Theory and Management June 28-30, 2010, St. Petersburg, Russia

It can be very hard for mathematicians trying to make their book stand out from all the other books on the subject ...
 

kay

Well-known member
Amy said:
Is it bad that this made sense to me?
It makes sense to me too ;)
Do you happen to have the full text of that presentation, Kay? I'd love to read it. I dont have access to the university library anymore =(

It's a pdf downloadable from the internet. Google on a selection of terms including Breisch  cave game theory and so on and see if you can find it. If not, pm me with your email address and I'll send it as an attachment. It's the entire conference proceedings, the Breisch references are on p8
 

graham

New member
Tony_B said:
Anyone going to own up to being "Mr. C J Binding", then? I just love that review.

If it was actually him, he has already posted on this thread. However, I have to say i don't know him, I've never met him & I don't remember him buying me beer last Saturday week.
 

tony from suffolk

Well-known member
If you took this book caving you'd need another copy to help you find the copy you think you put on a rock just now and can't seem to locate. Then you'd need another...
 
Thanks for the reference, Kay.

So now we see that the book is the outcome of 45 years' cogitation on the original article:

Breisch, R. (1967). An intuitive approach to speleotopology. Southwestern Cavers, VI, 72-78.

Sadly, the British Caving Library doesn't hold that journal (published by the Southwestern Region of the National Speleological Society), although it does have a number of articles by Richard L.Breisch ( http://caving-library.org.uk/catalogue/journals/author/breisch ) A Google search suggests that the article has been well cited in 'the literature' (89 times according to Google Scholar).

So this topic does seem to be in the wrong section...
 
Top