## Freesteel Blog » Tensioned thread theory

Friday, October 3rd, 2008 at 1:05 pm

Here’s a computational geometric problem I found in the course of work with no obvious good algorithm to solve it.

Take this picture below. The dotted line provides orientation and shows you where the endpoints are. We’ve got red dots and blue dots, and we start with a green piece of string threaded above the red dots and below the blue dots. (We can assume it’s in order along the orientation of the dotted line.)

Now pull the green string tight through those endpoints to get a nice zig-zaggy result like so:

I need a clean algorithm that will get to this answer. For the moment I am confounded.

The actual problem relates to smoothing a 5-axis milling machine toolpath with respect to one of its rotational axes while avoiding collisions. For this, the situation is a little more complex (I don’t want to calculate the positions of the blue and red points unless I absolutely have to), but an answer to the simplified version could lead the way.

Meanwhile, out in the real computational geometry world where there are professors, you’ll discover endless amounts of study of a similar, but somewhat less interesting problem of finding the convex hull of a set of points.

To get to this uninteresting problem, simply throw away all the red points and put the starting line all on one side.

The algorithm for pulling the red dotted line tight to get to the green line over all the points is easy to see: Consider each sequence of three points in order; if the middle point is below the line joining the other two points, then delete it.

If you run this trivial algorithm twice, once for above and once for below, and you started by finding the extreme left and right end points, you get Andrew’s Monotone Chain Algorithm for the convex hull of a set of points, published in 1979.

Finding the convex hull of a set of points has occupied quite a bit of attention over the years. We start with the Graham scan of 1972, the Jarvis march gift wrapping algorithm of 1973, the Alk-Toussaint heuristics of 1978, the Kirpatrick-Seidel algorithm of 1986, and Chan’s algorithm of 1996.

Never has so much mathematical honour been accorded for so little over so many years as has been the case for the computation of convex hulls. New students come to this field and wonder what the hell the whole fuss is about, because it looks just obvious. It is obvious. All the algorithms are pretty much O(nlogn) because they apply a sort function at some point and, in my opinion, are absolutely equivalent. The later advances merely involved partitioning the points into smaller sets, finding the convex hull for each set individually, and merging the result.

As these students grow older and eventually become professors, they realize what the game is, which is to have an easy life in a comfy job doing stuff that isn’t very hard, but just looks like it is because it has lots of equations so no one is going to say it’s silly. At least not anywhere that matters. (Blogs don’t count.)

The last thing you want is for anyone to find an application in your area. You don’t want some random machine tool programmer coming along and saying: “Oh, you look like the sort of person who ought to be able to solve this computational geometric problem I have here,” because they might find you out.

I can rephrase the problem in terms of the fruitful convex hull situation:

I want to see a slick algorithm to go from this:

to this:

where the string is pulled tight, with the blue birch trees on the inside and the red maple trees on the outside of the perimeter.

Then you can get one of your colleagues to name it after you (if your name sounds cool enough), and then later, after they’ve done something with one of the numerous variations of the problem (eg higher dimensions — the string passes through a set of polygons in space — or made-up geometries), you can return the favour by naming their invention after them.

But be warned. The older professors are going to say, “No no no no no. You don’t understand. Convex hull algorithms are the foundation stone of all computational geometry for the last thirty years.” Let’s not be too hasty and get beyond into stuff involving tori, and triangulations, and hundreds of other things it would be useful for someone to look at. You wouldn’t want the subject to become too difficult and sophisticated by the time you grow up. Next you’ll be telling me I should be releasing my code under some new-fangled public license so other people can make advances on it, and that I shouldn’t be using FORTRAN, which is a perfectly good language, I’ll tell you, because it makes moderately straightforward things into a terribly complex scramble without any effort. I am not going to put up with you telling me that your sloppy Python language is so much better and that I should learn something new. You young people always think you know everything.

The point of a university academic is to produce papers. You’re not supposed to get involved with any curious applications that are someone else’s problem. Unless they pay you. And you certainly don’t want to be maintaining libraries of free software functions in use out there in the wider world, like it is some kind of public service.

* Have I mentioned how many implementations of the quartic equation I believe are out there in the industry? I keep wanting someone in a university to maintain a really good one, and part-exchange it for the copies of this routine implemented in all the different CADCAM systems in the world, and do a sort of interesting archaeological code-study on them.

The researcher wouldn’t actually need to write their own. They’d only have to pick the one which is the best. The game is that all the CADCAM companies have a version of this and many other fundamental algorithms, and nobody knows who has the best. But if ten companies all got together and put their implementations into a pot and chose the best, each one would have a 90% chance of improvement in efficiency for free in each case.

Usually, the companies who are most unwilling to consider this game — even as a thought experiment — are the ones with the worst quality software. It’s the lack of curiosity that’s the give-away. They guard their source code jealously, because “someone might learn a secret from it and gain a competitive advantage”, yet they are the last ones who would ever comb through someone else’s code if they got access to it.

As with a lot of concealed secrets in business, the real revelation is that there’s nothing there. It’s just a game of Poker. Fun, but a waste of time, ultimately. It would be nice if someone clever went round the table telling everyone what to play so we could all win big against the House. It’d be more fun for those who want to move things forwards, rather than just maximizing the money. Eh?