OJ Board

Hi everyone,

Please, give me your opinion in Computational Geometry in WF.

In WF 2005, Voronoi diagram is actually not needed for problem B. However, would you ever expect in the WF to implement very hard geometry algorithms, such as: polygon trangulation, Delaunay trianglulation, closest/furthest Voronoi diagram, segment intersections, 3D Hull, segment tree search ?

These algorithms were introduced not in great details in my classes. I don't know how to handle special cases.

Kind regards,

Nhan

In general, I wouldn't expect most of these to occur. In more detail:

- Line segment intersection, even with all the special cases, occurs in ACM contests from time to time, it's best to have it pre-written

- In the World Finals the time limits are not too strict. Sometimes it is the case that you don't need an asymptotically optimal solution to get AC. E.g., I can imagine a problem, where you need to implement Voronoi's diagram, but O(N^2 log N) is still fast enough. Similarly, polygon triangulation is not that hard if the time limit admits an O(N^2) solution

- Other geometrical problems one can expect: some sweeping-line problems (e.g., area/perimeter of the union of some rectangles), and problems, where doing the geometry is only a part of the problem (e.g., using DP to find a triangulation where the sum of the used diagonals' lengths is minimal).

misof wrote:In general, I wouldn't expect most of these to occur.

Please, tell me what you think might occur. What algorithms should be prewritten ?

misof wrote: Line segment intersection, even with all the special cases.

My team is working on the special cases. This is quite nasty.

misof wrote: In the World Finals the time limits are not too strict. Sometimes it is the case that you don't need an asymptotically optimal solution to get AC. E.g.,

Please, give us more details.

misof wrote: Voronoi's diagram, but O(N^2 log N) is still fast enough.

I might be wrong but the flip edge method to find Delaunay Triangulation is in O(n^2). And, I have seen people implemented it in a regional.

To Misof: are you competing in the world final in 2006 ?

First of all, I'm not competing in these World Finals, I'm a bit too old for that I did compete in 2003.
( http://icpc.baylor.edu/dmt/media/indexe ... BLO%5D.jpg )

ThanhNhan wrote:

misof wrote:In general, I wouldn't expect most of these to occur.

Please, tell me what you think might occur. What algorithms should be prewritten ?

Basically, you should prepare code for difficult algorithms you have already encountered on various ACM contests. Here "difficult" means "having a lot of special cases, hard to get it right during a contest".

There are too many different things to consider. I recommend to prepare a bunch of geometric primitives (e.g., distance point-line segment, circumcircle center), one advanced data structure (such as a red-black tree / splay tree), some stringological algorithms (suffix array, KMP), and some maths (extended Euclid's algorithm).

ThanhNhan wrote:

misof wrote: Line segment intersection, even with all the special cases.

My team is working on the special cases. This is quite nasty.

If the segments are not parallel, there is at most one intersection point.
If they are parallel, check whether they are on the same line. If not, there is no intersection. If yes, you are left with a 1D case that can be reduced to finding the intersection of two intervals.

When writing 2D geometry, I'm used to use complex<long long> or complex<double> to represent points/vectors and my segment intersection function returns a vector< complex<sth> >.

ThanhNhan wrote:

misof wrote: Voronoi's diagram, but O(N^2 log N) is still fast enough.

I might be wrong but the flip edge method to find Delaunay Triangulation is in O(n^2). And, I have seen people implemented it in a regional.

Almost true. I think the expected time is O(N^2).

I think he was refering to finding the intersections of n segments in O(n log n + k) where k is the number of intersections, not to the intersection of two segments.

Cosmin.ro wrote:I think he was refering to finding the intersections of n segments in O(n log n + k) where k is the number of intersections, not to the intersection of two segments.

Possibly. I agree that this one is really nasty.

misof wrote:

Cosmin.ro wrote:I think he was refering to finding the intersections of n segments in O(n log n + k) where k is the number of intersections, not to the intersection of two segments.

Possibly. I agree that this one is really nasty.

Ha, I was talking about O((n+k) log n). There are 2 annoying cases: 3 or more segments intersect at the same point, or vertical segment.

misof wrote:First of all, I'm not competing in these World Finals, I'm a bit too old for that I did compete in 2003.
( http://icpc.baylor.edu/dmt/media/indexe ... BLO%5D.jpg )

You looked very young and bright in the picture.

We have what you suggested. Maybe, I just need to stop worrying.