Covex Hull, any ideas ?

[namgor]

Assume you are given the black box ConvexHull. The black box takes as input a list of n coordinates in the plane. The black box then computes the convex hull of these points, and returns a list of the vertices of the convex hull in clockwise order starting at an arbitrary vertex.

Use the ConvexHull black box to design an algorithm that sorts a list of n distinct integers. Provide pseudocode for your algorithm, and a brief argument that your explanation is correct.

------------------
DHAHL3seasons GP:73 G:121 A:55 Pts:176 GWG:12 +/-:184
UWSWA1season GP:9 G:12 A:8 Pts:20 GWG:3 +/-:-3
MCBHL1season GP:3 G:5 A:4 Pts:9 GWG:0 +/-:10

uwcdc.com (http://www.uwcdc.com) or namgor.com (http://www.namgor.com)

[bryce777]

I assume this is in 2 dimensions or it makes no sense.

What you would do is make a bunch of points that have (n1,0) (n2,0) etc.

Then you feed it into the black box. It will return it sorted, but the starting point will not be right.

Then, you simply step through, and find the highest or lowest point. From there it is simply a matter of moving the information into the right spot in the resulting array or whatever, or swapping it into the right places in the structure you passed in.

The pseudocode should be easy for you to fill in on your own if my explanation makes sense to you. Your will have to supply the justification for yourself, too http://www.sharkyforums.com/ubb/smile.gif

Originally posted by namgor:
Assume you are given the black box ConvexHull. The black box takes as input a list of n coordinates in the plane. The black box then computes the convex hull of these points, and returns a list of the vertices of the convex hull in clockwise order starting at an arbitrary vertex.

Use the ConvexHull black box to design an algorithm that sorts a list of n distinct integers. Provide pseudocode for your algorithm, and a brief argument that your explanation is correct.





------------------
system specs:
Voodoo 5 5500 agp
tyan 1834d tiger 133 dual 800eb 133mhz FSB
via chipset kx133 via apollo pro (don't make this mistake)
256 MB RAM
2 maxtor 60gig ata100 drives
promise ata100 controller
liteon 52 truex cdrom
Linksys ethernet 10/100
Soundblaster Live! (what's so exciting about it??) value edition
300watt power supply (inwin)
about 7 pounds of fans (I'm not kidding)
Suse 7.1(god gnome is crappy compared to CDE)/win2000 based system

[namgor]

this is indeed a smart algorithm! thanks

------------------
DHAHL3seasons GP:73 G:121 A:55 Pts:176 GWG:12 +/-:184
UWSWA1season GP:9 G:12 A:8 Pts:20 GWG:3 +/-:-3
MCBHL1season GP:3 G:5 A:4 Pts:9 GWG:0 +/-:10

uwcdc.com (http://www.uwcdc.com) or namgor.com (http://www.namgor.com)

[namgor]

I wanted to follow up, placing a points in a line will form ambigious clockwise definition. Hard to explain it here without graphics utilities.

Anyway, I now map 2 sets of points into the plane and form a rectangle, then do pretty much same as you said.

------------------
DHAHL3seasons GP:73 G:121 A:55 Pts:176 GWG:12 +/-:184
UWSWA1season GP:9 G:12 A:8 Pts:20 GWG:3 +/-:-3
MCBHL1season GP:4 G:5 A:5 Pts:10 GWG:0 +/-:9

UWSWA 2nd season start Sept 24,01
uwcdc.com (http://www.uwcdc.com) or namgor.com (http://www.namgor.com)