An efficient algorithm for decomposing a polygon into star-shaped polygons

D. Avis; G. T. Toussaint

doi:10.1016/0031-3203(81)90002-9

An efficient algorithm for decomposing a polygon into star-shaped polygons

D. Avis, G. T. Toussaint

Computer Science

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

Abstract

In this paper we show how a theorem in plane geometry can be converted into a O(n log n) algorithm for decomposing a polygon into star-shaped subsets. The computational efficiency of this new decomposition contrasts with the heavy computational burden of existing methods.

Original language	English (US)
Pages (from-to)	395-398
Number of pages	4
Journal	Pattern Recognition
Volume	13
Issue number	6
DOIs	https://doi.org/10.1016/0031-3203(81)90002-9
State	Published - 1981

Keywords

Colouring algorithms
Computational geometry
Polygonal decomposition
Star-shaped polygons
Syntactic pattern recognition
Triangulation

ASJC Scopus subject areas

Software
Signal Processing
Computer Vision and Pattern Recognition
Artificial Intelligence

Access to Document

10.1016/0031-3203(81)90002-9

Cite this

@article{595fd1166b504516a86ba84e421461f3,

title = "An efficient algorithm for decomposing a polygon into star-shaped polygons",

abstract = "In this paper we show how a theorem in plane geometry can be converted into a O(n log n) algorithm for decomposing a polygon into star-shaped subsets. The computational efficiency of this new decomposition contrasts with the heavy computational burden of existing methods.",

keywords = "Colouring algorithms, Computational geometry, Polygonal decomposition, Star-shaped polygons, Syntactic pattern recognition, Triangulation",

author = "D. Avis and Toussaint, {G. T.}",

note = "Funding Information: supported by N.S.E.R.C. grants Nos A-3013",

year = "1981",

doi = "10.1016/0031-3203(81)90002-9",

language = "English (US)",

volume = "13",

pages = "395--398",

journal = "Pattern Recognition",

issn = "0031-3203",

publisher = "Elsevier Limited",

number = "6",

}

TY - JOUR

T1 - An efficient algorithm for decomposing a polygon into star-shaped polygons

AU - Avis, D.

AU - Toussaint, G. T.

N1 - Funding Information: supported by N.S.E.R.C. grants Nos A-3013

PY - 1981

Y1 - 1981

N2 - In this paper we show how a theorem in plane geometry can be converted into a O(n log n) algorithm for decomposing a polygon into star-shaped subsets. The computational efficiency of this new decomposition contrasts with the heavy computational burden of existing methods.

AB - In this paper we show how a theorem in plane geometry can be converted into a O(n log n) algorithm for decomposing a polygon into star-shaped subsets. The computational efficiency of this new decomposition contrasts with the heavy computational burden of existing methods.

KW - Colouring algorithms

KW - Computational geometry

KW - Polygonal decomposition

KW - Star-shaped polygons

KW - Syntactic pattern recognition

KW - Triangulation

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

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

U2 - 10.1016/0031-3203(81)90002-9

DO - 10.1016/0031-3203(81)90002-9

M3 - Article

AN - SCOPUS:0019680822

SN - 0031-3203

VL - 13

SP - 395

EP - 398

JO - Pattern Recognition

JF - Pattern Recognition

IS - 6

ER -

An efficient algorithm for decomposing a polygon into star-shaped polygons

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this