Triangulating a simple polygon in linear time

Research output: Contribution to journalConference articlepeer-review

50 Scopus citations


A linear-time deterministic algorithm for triangulating a simple polygon is developed. The algorithm is elementary in that it does not require the use of any complicated data structures; in particular, it does not need dynamic search trees, finger trees, or fancy point location structures.

Original languageEnglish (US)
Pages (from-to)220-230
Number of pages11
JournalIEEE Transactions on Industry Applications
Issue number1 pt 1
StatePublished - Jan 1991
Externally publishedYes
Event1989 Industry Applications Society Annual Meeting - San Diego, CA, USA
Duration: Oct 1 1989Oct 5 1989

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Triangulating a simple polygon in linear time'. Together they form a unique fingerprint.

Cite this