wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Polygon
        
(Message started by: gotit on Aug 31st, 2007, 1:38pm)
Title: Polygon
Post by gotit on Aug 31st, 2007, 1:38pm
You are given cordinates of n points on a plane and you are asked to draw a polygon through some or all of these points such that no point lies outside the polygon.What algorithm should be used?Also,the polygon should have the minimum number of sides possible.
Title: Re: Polygon
Post by Barukh on Aug 31st, 2007, 10:57pm
Convex Hull (http://en.wikipedia.org/wiki/Convex_hull#Computation_of_convex_hulls)?
Title: Re: Polygon
Post by Aryabhatta on Aug 31st, 2007, 11:34pm
Convex Hull is probably the intent, but the wording makes it seem like finding a triangle passing through one of the points will do, which i guess can be done on O(n) time.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board