Re: Area Of Triangle

On Jul 9, 5:20 pm, silentsiren1987 <sushant.singh1...@xxxxxxxxx>
wrote:
Hello ,

I am trying to find the triangle with maximum area , from a given set of 'n' integer co-ordinates of the form x,y .
Only problem is 'n' is huge ( of the order of 10^6) so i have to use an efficient method.

So i constructed a convex hull from the given n points. Now i have the vertices of the convex polygon and i need to calculate the area of the maximum triangle.

Is it correct that if i choose any two vertices of the convex hull and then loop over the remaining vertices one by one , every time calculating the area and marking the one with the maximum area , i will get the right answer?
If not please correct me .

thanks

Hi, silentsiren1987:

Yes, that will try all the possibilities,
which increase in number with the cube
of the vertex count on the convex hull.

In a recent thread in this sci.math
newsgroup, the same problem had a
solution which requires checking only
a number of possibilities that rises
with the square of the number of vertices
on the convex hull:

http://groups.google.com/group/sci.math/browse_frm/thread/acb6e5960e4c05c4/86f79e7fc8d02eaa

See the method of solution proposed by
James Waldby there!

regards, chip
.

Relevant Pages

  • Re: Triangle with largest area in a convex polygon
    ... triangle having the greateset area that can be formed using any 3 of ... previous "Triangle with maximum area using given lattice points"? ... polygon = convex hull. ...
    (sci.math)
  • Re: O(n log n) algorithm to find maximum area of a triangle in a convex hull
    ... How can we compute the area of a triangle in O ... [On a Triangle with the Maximum Area in a Planar Point Set] ... [CGAL Open Source Project] ... and has a worst case running time of O(k · n + n · log n), ...
    (sci.math)
  • Re: Triangle inside an ellipsoid
    ... >> The triangle lies in the x-y plane if c is the smallest. ... >> We can transform the ellipse into a cirle by stretching the y ... >> The maximum area of the triangle inside this circle is a equilateral ... >> Transform the cirle back to the ellipse by mutiplying a factor of b/a. ...
    (sci.math)
  • Re: Triangles Inscribed in a Circle
    ... in a circle C. ... triangle A'BC (or AB'C, ... proved that the equilateral triangle has the maximum area. ... there exists an inscribed triangle with larger area. ...
    (sci.math)
  • Re: Area of X^2*n+Y^2*n=a^2*n
    ... > What the maximum area of a triangle inside this superellipse ... but that's a pure guess. ... Prev by Date: ...
    (sci.math)
Quantcast