Quote:
Originally Posted by RustyBrooks
Right, the segment-by-segment intersection will be h^2 which in it's worst case is n^2 because you can imagine degenerate sets where the points are already forming their own convex hull. It's definitely a good and simple method and if I was actually going to *program* this it might be where I started. A lot of the time it'll be reasonably perfomant because in a lot of cases "h" is a lot smaller than "n"
On a completely unrelated note, the way I found out about or got into computational geometry is that I was a network administrator for the EE/CS building, and one of the guys I worked with a lot was a PhD student who was working on the "museum guard*" problem. He needed a way to generate polygons that wasn't "biased" in any way, i.e. it needed to generate polygons of all types, i.e. a method that didn't accidentally show bias towards one kind of polygone over another. I don't actually know how hard this problem was but I thought of a solution and I showed him and he convinced me/helped me write a short paper about it. After that I started studying the field and writing more papers in it.
* the museum guard problem is fairly well known so maybe you've heard of it. Basically imagine a museum room that is defined by some polygon. Pick 2 points A and B on the polygon. There are 2 guards, both start at A and walk to B, each along their own side of the polygon. They must stay in line-of-sight of each other the whole way
That’s interesting, I never heard of that.
I’m basically going to create one hull for one set, and test if the points in the other set fall inside the first hull.
I could create two hulls and just test those points, might be faster, idk.
I found a method for testing if a point falls inside of a polygon inside of a 1978 thesis paper, and it is log n. I asked if I could just use this method in my homework and credit the source, and I got kind of a shaky “yes” from the professor. Not sure what else to do really because there’s no way I could have come up with that algorithm on my own, or if it’s just sufficient to describe my algorithm as “test if a point falls inside of this hull, which is log n.”
Anyway, thank you, i’ll undoubtedly have more questions and will post in the hw thread from now on, sorry for derail