## Need expert's view for geometry algos.

Moderator: Board moderators

Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA

### Need expert's view for geometry algos.

I know the following algo's & implemented them correctly in some problems of UVa. I want to know if better algos exists.I want to mention as far as i know:

1.Convex hull->O(nlog n):Graham Scan.
2.Point inside a polygon->O(n):Crossing number method.
3.Center of Gravity(UVa 10002)->O(nlog n).
4.Finding closest pair of points->O(nlog n).
5.From a large number of points,what is the number of maximum points on a line->O(n^2*log (n^2)).
6.Minimum circle enclosing n points->O(nlog n)+O(h^3),where h is the number of points on convex-hull.
7.Line segment intersection.

I want to know what should i learn more,because i am going to participate in the Dhaka regional-07.Should i learn line clipping(Cohen-Sutherland),common area of two polygon,trelayny triangulation,voronoi diagram etc.?Please mention any useful links,books etc.I wiil be very glad if u also mention the best run time of the algo's.Thanks in advance.

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
Your knowledge about some geometrical algorithm is good but you have to know that writing an geometrical program is not just knowledge, You should learn how your code covers all of the special cases which happen in almost of geometry problems. In the other words you have to have a good insight for such these problems. Most of geometry-problems in ACM-ICPC just need a slight knowledge of geometry. Their solutions don't need advanced algorithms instead, they need a creative mind. You should learn how to utilize these algorithms together.
I suggest you keeping on solving and thinking about geometrical problems without seeking about an exact algorithm on the net, in this way you could solve almost all of ACM-ICPC problems.

Nevertheless, there is a very good book on Computational Geometry, from springer. It is an excellent book, but I don't think it is a good book for an ACM problem-solver who wants to learn Computational Geometry just for a regional contest.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I agree with Moha, you usually don't need advanced geometric algorithms in ACM ICPC. Creativity, and ability to quickly and correctly implement basic algorithms (like lines/segments/circles intersections, convex hull, sweeping line algoritms) are more important. Practice helps greatly here.

For convex hull I'd suggest to learn monotone chain algorithm. It's very simple, uses only integer operations (when coordinates are integers), and blazingly fast - the most expensive operation is just lexicographically sorting the input points (and that can be even done in O(n) with radix sort!)
Anindya wrote:I wiil be very glad if u also mention the best run time of the algo's
Many "best" algorithms often are very theoretical, and almost unimplementable in the limited contest time. Try to use simple enough algorithms that will work in the given amount of time. Anything O(n log n) is usually more than sufficient for any purpose...

Slightly off-topic, i've recently found this hilarious saying on algorithms complexity, and just can't not post it
...when we give a running time for an algorithm, what we're really doing - and what most theoretical computer scientists devote their entire careers doing - is bragging about how easy some problem is. This sometimes leads to long sequences of results that sound like an obscure version of "Name that Tune":

Lennes: "I can triangulate that polygon in O(n^2) time."
Shamos: "I can triangulate that polygon in O(n log n) time."
Tarjan: "I can triangulate that polygon in O(n log log n) time."
Seidel: "I can triangulate that polygon in O(n log^* n) time." [Audience gasps.]
Chazelle: "I can triangulate that polygon in O(n) time." [Audience gasps and applauds.]
"Triangulate that polygon!" Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA
mf,i can do graham scan & i got ac in almost all UVa problems of convex-hull.Should i learn that algo to avoid double calculation?My runtimes are also not so bad.Actually i wanted to know whether i should learn more algo's of geometry after seeing these ones:
688
691
10095
137
10084

Still i have not found a problem about finding common area of two polygons.But this algo is mentioned in Shahriar Manjoor's article.

Moha,u are quite right.for example,i solved 10089->it's a convex-hull problem,but it seemed impossible to me to have the idea.I went to board
& then solved it.Surely this is a wonderful problem.But is it possible to solve these type of things in contest time?

Actually i am not expert like u,doing acm for one year, so surely i have to learn still a lot.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
For intersection of two convex polygons see http://acm.uva.es/p/v1/137.html

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
Not that you'll ever need this on an ACM ICPC contest, but for the sake of completeness: maximum number of points on a line can be done in O(n^2) by using the point-line duality, and then traversing the plane subdivision and looking for the vertex of maximum degree.

Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA
misof,i can't realise what you told.
What is point-line duality? Can u explain ur process?
What i do is to generate all line segments & then sort them according to their slope.Then count number of max occurence of a slope.Say this number is M,then ans*(ans-1)/2=M.I find ans fom this.

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
137 mf has described it.
688 Is a simple sweepline problem.
691 I tried it two years ago, but in vain. (may be the precision?!)
10084 needs clipping. since the polygon is convex, the clipping is very simple.
10095 I don't know, even I haven't read it before. I should think!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
10095 is finding minimum sphere enclosing n points.
There is a O(n) algorithm to solve it. I think O(n log n) should be enough for this problem.

Here's what I know:
1.Convex hull->O(nlog n):Graham Scan.
O(n log n) is known to be optimal if input values are unbounded.

2.Point inside a polygon->O(n):Crossing number method.
O(log n) is possible for convex polygons.

3.Center of Gravity(UVa 10002)->O(nlog n).
This has the same complexity of finding area of polygon, which is only O(n). But we need to first find the polygon first in O(n log n)

4.Finding closest pair of points->O(nlog n).
I don't know if O(n log n) is optimal or not. But the closest pair must be an edge in the delaunay triangulation

5.From a large number of points,what is the number of maximum points on a line->O(n^2*log (n^2)).
O(n^2) is sufficient to construct the dual.

6.Minimum circle enclosing n points->O(nlog n)+O(h^3),where h is the number of points on convex-hull.
O(n) is optimal for this problem, but for all purposes, O(n log n) using furthest point voronoi diagram is sufficient. The center will be either a vertex or on an edge of the diagram.

7.Line segment intersection.
I thought intersection of 2 line segments is O(1)
Intersection of n line segments is O(n log n + k) where k is number of intersections. This is done by using a well known sweepline algorithm.

It is known that intersection of 2 arbitrary polygons is O(nlog n + k) using sweepline, but if both convex, then it is O(n)

gawry
New poster
Posts: 19
Joined: Fri Aug 02, 2002 5:54 pm
sclo wrote: 6.Minimum circle enclosing n points->O(nlog n)+O(h^3),where h is the number of points on convex-hull.
O(n) is optimal for this problem, but for all purposes, O(n log n) using furthest point voronoi diagram is sufficient. The center will be either a vertex or on an edge of the diagram.
There is also a beautifully simple O(n) randomized algorithm (http://citeseer.ist.psu.edu/welzl91smallest.html), certainly much simplier than Voronoi diagram .

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
sclo wrote:6.Minimum circle enclosing n points->O(nlog n)+O(h^3),where h is the number of points on convex-hull.
O(n) is optimal for this problem, but for all purposes, O(n log n) using furthest point voronoi diagram is sufficient. The center will be either a vertex or on an edge of the diagram.
Does it mean it could be O(N^3) in its worst case?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
Moha wrote:
sclo wrote:6.Minimum circle enclosing n points->O(nlog n)+O(h^3),where h is the number of points on convex-hull.
O(n) is optimal for this problem, but for all purposes, O(n log n) using furthest point voronoi diagram is sufficient. The center will be either a vertex or on an edge of the diagram.
Does it mean it could be O(N^3) in its worst case?
If you use the convex hull to compute it, then it is O(n^3) in worst case.
If you first compute the furthest point voronoi diagram in time O(n log n), then it is O(n) since voronoi diagram has size O(n).
If you use the randomized algorithm, it is expected O(n)
If you use the complicated linear algorithm, then it is O(n)

Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA
First of all, i thank everyone for making a good response.
As i have an exam tomorrow,now i can't do the problems or read the algo's you mentioned.But i will try to do these as soon as I can.
The problem is learning an algo does not ensure that i am able to solve the problem,specially in geometry.But i will try.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
misof wrote:Not that you'll ever need this on an ACM ICPC contest, but for the sake of completeness: maximum number of points on a line can be done in O(n^2) by using the point-line duality, and then traversing the plane subdivision and looking for the vertex of maximum degree.
Or better yet, with simple hashing.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA
mf wrote:
For convex hull I'd suggest to learn monotone chain algorithm. It's very simple, uses only integer operations (when coordinates are integers), and blazingly fast

I have done Graham-Scan without any double operations.I have got ac in 10078->The Art Gallery with my integer implementation of Graham - Scan.