15 views

Skip to first unread message

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.

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

===============================================================================

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.

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.

>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

Search

Clear search

Close search

Google apps

Main menu