Correction to: A Linear-Time Algorithm for Triangulating a Simple Polygon (Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (1986) (380-388) DOI: 10.1145/12130.12170)

Robert E. Tarjan; Christopher J. Van Wyk

doi:10.1109/SFCS.1987.16

Correction to: A Linear-Time Algorithm for Triangulating a Simple Polygon (Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (1986) (380-388) DOI: 10.1145/12130.12170)

Robert E. Tarjan
, Christopher J. Van Wyk

Research output: Contribution to journal › Comment/debate › peer-review

Abstract

The analysis showing that our triangulation algorithm runs in linear time is incorrect, and indeed the algorithm does not run in linear time in the worst case. So far we have been unable to obtain a linear-time algorithm for the triangulation problem. We have been able to obtain an 0 (n loglogn)-time algorithm, however. The details are described in,cAn O(n loglogn)-Time Algorithm for Triangulating a Simple Polygon," SIAM Journal on Computing 17, 1 (February, 1988), to appear.

Original language	English (US)
Pages (from-to)	486
Number of pages	1
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs	https://doi.org/10.1109/SFCS.1987.16
State	Published - 1987
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science

Access to Document

10.1109/SFCS.1987.16

Cite this

@article{03f0466138094140889aac6b4b337e76,

title = "Correction to: A Linear-Time Algorithm for Triangulating a Simple Polygon (Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (1986) (380-388) DOI: 10.1145/12130.12170)",

abstract = "The analysis showing that our triangulation algorithm runs in linear time is incorrect, and indeed the algorithm does not run in linear time in the worst case. So far we have been unable to obtain a linear-time algorithm for the triangulation problem. We have been able to obtain an 0 (n loglogn)-time algorithm, however. The details are described in,cAn O(n loglogn)-Time Algorithm for Triangulating a Simple Polygon,{"} SIAM Journal on Computing 17, 1 (February, 1988), to appear.",

author = "Tarjan, \{Robert E.\} and \{Van Wyk\}, \{Christopher J.\}",

year = "1987",

doi = "10.1109/SFCS.1987.16",

language = "English (US)",

pages = "486",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

publisher = "IEEE Computer Society",

}

Correction to: A Linear-Time Algorithm for Triangulating a Simple Polygon (Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (1986) (380-388) DOI: 10.1145/12130.12170). / Tarjan, Robert E.; Van Wyk, Christopher J.
In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 1987, p. 486.

Research output: Contribution to journal › Comment/debate › peer-review

TY - JOUR

T1 - Correction to

T2 - A Linear-Time Algorithm for Triangulating a Simple Polygon (Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (1986) (380-388) DOI: 10.1145/12130.12170)

AU - Tarjan, Robert E.

AU - Van Wyk, Christopher J.

PY - 1987

Y1 - 1987

N2 - The analysis showing that our triangulation algorithm runs in linear time is incorrect, and indeed the algorithm does not run in linear time in the worst case. So far we have been unable to obtain a linear-time algorithm for the triangulation problem. We have been able to obtain an 0 (n loglogn)-time algorithm, however. The details are described in,cAn O(n loglogn)-Time Algorithm for Triangulating a Simple Polygon," SIAM Journal on Computing 17, 1 (February, 1988), to appear.

AB - The analysis showing that our triangulation algorithm runs in linear time is incorrect, and indeed the algorithm does not run in linear time in the worst case. So far we have been unable to obtain a linear-time algorithm for the triangulation problem. We have been able to obtain an 0 (n loglogn)-time algorithm, however. The details are described in,cAn O(n loglogn)-Time Algorithm for Triangulating a Simple Polygon," SIAM Journal on Computing 17, 1 (February, 1988), to appear.

UR - https://www.scopus.com/pages/publications/105032161783

UR - https://www.scopus.com/pages/publications/105032161783#tab=citedBy

U2 - 10.1109/SFCS.1987.16

DO - 10.1109/SFCS.1987.16

M3 - Comment/debate

AN - SCOPUS:105032161783

SN - 0272-5428

SP - 486

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

ER -

Correction to: A Linear-Time Algorithm for Triangulating a Simple Polygon (Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (1986) (380-388) DOI: 10.1145/12130.12170)

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this