A COUNTER－EXAMPLE TO A FAST ALGORITHM FOR FINDING THE CONVEX HULL OF A SIMPLE POLYGON A COUNTER-EXAMPLE TO A FAST ALGORITHMFOR FINDING THE CONVEX HULLOF A SIMPLE POLYGON期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

A COUNTER－EXAMPLE TO A FAST ALGORITHM FOR FINDING THE CONVEX HULL OF A SIMPLE POLYGON

摘要：	ＡＣＯＵＮＴＥＲ－ＥＸＡＭＰＬＥＴＯＡＦＡＳＴＡＬＧＯＲＩＴＨＭＦＯＲＦＩＮＤＩＮＧＴＨＥＣＯＮＶＥＸＨＵＬＬＯＦＡＳＩＭＰＬＥＰＯＬＹＧＯＮＧｏｄｆｒｉｅｄＴｏｕｓｓａｉｎｔＡＣＯＵＮＴＥＲ－ＥＸＡＭＰＬＥＴＯＡＦＡＳＴＡＬＧＯＲＩＴＨＭＦＯＲＦＩ...
A COUNTER-EXAMPLE TO A FAST ALGORITHMFOR FINDING THE CONVEX HULLOF A SIMPLE POLYGON

Authors:	Godfried Toussaint

Affiliation:	Godfried Toussaint

Abstract:	A linear-time algorithm was recently published (International Conference Proceedings ofPacific Graphics' 94/CADDM' 94, August 26-29 , 1994 , Beijing , China) for computing the convexhull of a simple polygon. In this note we present a counter-example to that algorithm by exhibiting afamily of polygons for which the algorithm discards vertices that are on the convex hull.

Keywords:	simple-polygons crossing-polygons convex-hull algorithms Graham-scan computa-tional geometry
本文献已被 CNKI 等数据库收录！