Need Algorithm for n-convex bounding polygon

15 views
Skip to first unread message

Hein Veenhof

unread,
Aug 24, 1993, 4:25:41 AM8/24/93
to
I'am looking for an algorithm that will generate a n-convex hull
of a concave polygon.
This convex hull must have exactly n vertices.

A polygon can always be approximated by a triangle, so there is
a lower bound 3 for n. I assume there is also an upper bound for
n. Other approximations are e.g. 4-corner, 5-corner etc..

Who is familiar with algorithms for generating convex hulls ?
Is it possible to have these algorithms generate a convex hull with
exactly n vertices ?
Who knows of a reference to such an algorithm ?


Please reply soon.


===============================================================================
Ir. Hein M. Veenhof email: vee...@cs.utwente.nl
University of Twente phone: ++31 (0)53 893763
Dept. of Computer Science fax : ++31 (0)53 339605
mail : P.O. Box 217
7500 AE Enschede
The Netherlands
===============================================================================

Who? Me? Do you really mean me?

unread,
Aug 24, 1993, 7:36:13 AM8/24/93
to
vee...@cs.utwente.nl (Hein Veenhof) writes:

& I'am looking for an algorithm that will generate a n-convex hull
& of a concave polygon.
& This convex hull must have exactly n vertices.

& A polygon can always be approximated by a triangle, so there is
& a lower bound 3 for n. I assume there is also an upper bound for
& n. Other approximations are e.g. 4-corner, 5-corner etc..

& Who is familiar with algorithms for generating convex hulls ?
& Is it possible to have these algorithms generate a convex hull with
& exactly n vertices ?
& Who knows of a reference to such an algorithm ?


& Please reply soon.


& ===============================================================================
& Ir. Hein M. Veenhof email: vee...@cs.utwente.nl
& University of Twente phone: ++31 (0)53 893763
& Dept. of Computer Science fax : ++31 (0)53 339605
& mail : P.O. Box 217
& 7500 AE Enschede
& The Netherlands
& ===============================================================================

If you take a polygon whose normal convex hull has exactly 3 vertices, you
cannot find a smallest convex quadrilateral enclosing the polygon.
3 of your 4 vertices will be vertices of the convex hull, and whereever you
pick the fourth vertex of the quadrilateral, there will be another point
closer to the original convex hull. ( I assume degenerated cases where the
convex quadrilateral has 3 colinear points are forbidden.)

Haijo.

Joseph O'Rourke

unread,
Aug 24, 1993, 11:15:40 AM8/24/93
to
In article <1993Aug2...@cs.utwente.nl> vee...@cs.utwente.nl (Hein Veenhof) writes:
>I'am looking for an algorithm that will generate a n-convex hull
>of a concave polygon.
>This convex hull must have exactly n vertices.

What is an "n-convex hull"? For standard convex hulls, you
might start with Preparata and Shamos:


@book{Preparata.Shamos
, author = "F. P. Preparata and M. I. Shamos"
, title = "Computational Geometry: an Introduction"
, publisher = "Springer-Verlag"
, address = "New York, NY"
, year = "1985"
, keywords = "book"
, label = "PS-CGI-SV-85"
, note = "Corrected and expanded second printing, 1988."
}

Reply all
Reply to author
Forward
0 new messages