Points_in_Plane_Triangles

[Michael Hoffmann]

On Jun 18,  8:32am, Irwin Scollar wrote:
> Subject: Points_in_Plane_Triangles
> Given a large scatter of points bounded by a convex hull on a plane, find
> three points in the scatter which are the vertices of a triangle which has an
> area larger than that defined by any other set of three points.

If you are looking for an implementation, we have implemented a O(kn + n log n)
algorithm for finding the maximal (wrt area or perimeter) k-gon in the CGAL
library, see http://www.cs.uu.nl/CGAL

The implementation is based on an algorithm by Aggarwal et al, references
below. For the special case of maximum area triangles there is also a linear
algorithm by Dobkin and Snyder (not (yet;) in CGAL).

Best regards,
Michael Hoffmann
Theoretical Computer Science                email: hoffmann at inf.ethz.ch
ETH Zentrum, IFW B46.2                      phone: +41-1-6327390
CH-8092 Zurich, Switzerland                 fax:   +41-1-6321172

@inproceedings{ds-gmmmc-79
, author =	"D. P. Dobkin and L. Snyder"
, title =	"On a general method for maximizing and minimizing among
certain geometric problems"
, booktitle =	"Proc. 20th Annu. IEEE Sympos. Found. Comput. Sci."
, year =	1979
, pages =	"9--17"
}

@article{akmsw-gamsa-87
, author =	"A. Aggarwal and M. M. Klawe and S. Moran and P. W. Shor and R.
Wilber"
, title =	"Geometric applications of a matrix-searching algorithm"
, journal =	"Algorithmica"
, volume =	2
, year =	1987
, pages =	"195--208"
, keywords =	"polygons, furthest neighbors, convex polygons, routing"
, succeeds =	"akmsw-gamsa-86"
, update =	"98.07 agarwal, 96.09 agarwal, 96.05 agarwal, 95.05 korneenko"
}

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/threads.html.