On a convex hull algorithm for polygons and its application to triangulation problems

Godfried T. Toussaint; David Avis

doi:10.1016/0031-3203(82)90057-7

On a convex hull algorithm for polygons and its application to triangulation problems

Godfried T. Toussaint, David Avis

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

A frequently used algorithm for finding the convex hull of a simple polygon in linear running time has been recently shown to fail in some cases. Due to its simplicity the algorithm is, nevertheless, attractive. In this paper it is shown that the algorithm does in fact work for a family of simple polygons known as weakly externally visible polygons. Some application areas where such polygons occur are briefly discussed. In addition, it is shown that with a trivial modification the algorithm can be used to internally and externally triangulate certain classes of polygons in 0(n) time.

Original language	English (US)
Pages (from-to)	23-29
Number of pages	7
Journal	Pattern Recognition
Volume	15
Issue number	1
DOIs	https://doi.org/10.1016/0031-3203(82)90057-7
State	Published - 1982

Keywords

Algorithm
Computational complexity
Computational geometry
Convex hull
Image processing
Pattern recognition
Simple polygon
Triangulation Polygon decomposition
Weakly externally visible polygon

ASJC Scopus subject areas

Software
Signal Processing
Computer Vision and Pattern Recognition
Artificial Intelligence

Access to Document

10.1016/0031-3203(82)90057-7

Cite this

@article{ce7b74b02f9e4a079a4c7d8942408f67,

title = "On a convex hull algorithm for polygons and its application to triangulation problems",

abstract = "A frequently used algorithm for finding the convex hull of a simple polygon in linear running time has been recently shown to fail in some cases. Due to its simplicity the algorithm is, nevertheless, attractive. In this paper it is shown that the algorithm does in fact work for a family of simple polygons known as weakly externally visible polygons. Some application areas where such polygons occur are briefly discussed. In addition, it is shown that with a trivial modification the algorithm can be used to internally and externally triangulate certain classes of polygons in 0(n) time.",

keywords = "Algorithm, Computational complexity, Computational geometry, Convex hull, Image processing, Pattern recognition, Simple polygon, Triangulation Polygon decomposition, Weakly externally visible polygon",

author = "Toussaint, {Godfried T.} and David Avis",

year = "1982",

doi = "10.1016/0031-3203(82)90057-7",

language = "English (US)",

volume = "15",

pages = "23--29",

journal = "Pattern Recognition",

issn = "0031-3203",

publisher = "Elsevier Limited",

number = "1",

}

TY - JOUR

T1 - On a convex hull algorithm for polygons and its application to triangulation problems

AU - Toussaint, Godfried T.

AU - Avis, David

PY - 1982

Y1 - 1982

N2 - A frequently used algorithm for finding the convex hull of a simple polygon in linear running time has been recently shown to fail in some cases. Due to its simplicity the algorithm is, nevertheless, attractive. In this paper it is shown that the algorithm does in fact work for a family of simple polygons known as weakly externally visible polygons. Some application areas where such polygons occur are briefly discussed. In addition, it is shown that with a trivial modification the algorithm can be used to internally and externally triangulate certain classes of polygons in 0(n) time.

AB - A frequently used algorithm for finding the convex hull of a simple polygon in linear running time has been recently shown to fail in some cases. Due to its simplicity the algorithm is, nevertheless, attractive. In this paper it is shown that the algorithm does in fact work for a family of simple polygons known as weakly externally visible polygons. Some application areas where such polygons occur are briefly discussed. In addition, it is shown that with a trivial modification the algorithm can be used to internally and externally triangulate certain classes of polygons in 0(n) time.

KW - Algorithm

KW - Computational complexity

KW - Computational geometry

KW - Convex hull

KW - Image processing

KW - Pattern recognition

KW - Simple polygon

KW - Triangulation Polygon decomposition

KW - Weakly externally visible polygon

UR - http://www.scopus.com/inward/record.url?scp=0020045441&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0020045441&partnerID=8YFLogxK

U2 - 10.1016/0031-3203(82)90057-7

DO - 10.1016/0031-3203(82)90057-7

M3 - Article

AN - SCOPUS:0020045441

SN - 0031-3203

VL - 15

SP - 23

EP - 29

JO - Pattern Recognition

JF - Pattern Recognition

IS - 1

ER -

On a convex hull algorithm for polygons and its application to triangulation problems

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this