Parallel triangulation of a polygon in two calls to the trapezoidal map

Chee Keng Yap

doi:10.1007/BF01762118

Parallel triangulation of a polygon in two calls to the trapezoidal map

Chee Keng Yap

Computer Science

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

Abstract

We give a parallel method for triangulating a simple polygon by two (parallel) calls to the trapezoidal map computation. The method is simpler and more elegant than previous methods. Along the way we obtain an interesting partition of one-sided monotone polygons. Using the best-known trapezoidal map algorithm, ours run in time O(log n) using O(n) CREW PRAM processors.

Original language	English (US)
Pages (from-to)	279-288
Number of pages	10
Journal	Algorithmica
Volume	3
Issue number	1
DOIs	https://doi.org/10.1007/BF01762118
State	Published - Mar 1988

Keywords

Parallel algorithm
Polygon
Triangulation

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/BF01762118

Cite this

@article{34f0d5d723d34e8caba397df73d56349,

title = "Parallel triangulation of a polygon in two calls to the trapezoidal map",

abstract = "We give a parallel method for triangulating a simple polygon by two (parallel) calls to the trapezoidal map computation. The method is simpler and more elegant than previous methods. Along the way we obtain an interesting partition of one-sided monotone polygons. Using the best-known trapezoidal map algorithm, ours run in time O(log n) using O(n) CREW PRAM processors.",

keywords = "Parallel algorithm, Polygon, Triangulation",

author = "Yap, {Chee Keng}",

year = "1988",

month = mar,

doi = "10.1007/BF01762118",

language = "English (US)",

volume = "3",

pages = "279--288",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Parallel triangulation of a polygon in two calls to the trapezoidal map

AU - Yap, Chee Keng

PY - 1988/3

Y1 - 1988/3

N2 - We give a parallel method for triangulating a simple polygon by two (parallel) calls to the trapezoidal map computation. The method is simpler and more elegant than previous methods. Along the way we obtain an interesting partition of one-sided monotone polygons. Using the best-known trapezoidal map algorithm, ours run in time O(log n) using O(n) CREW PRAM processors.

AB - We give a parallel method for triangulating a simple polygon by two (parallel) calls to the trapezoidal map computation. The method is simpler and more elegant than previous methods. Along the way we obtain an interesting partition of one-sided monotone polygons. Using the best-known trapezoidal map algorithm, ours run in time O(log n) using O(n) CREW PRAM processors.

KW - Parallel algorithm

KW - Polygon

KW - Triangulation

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

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

U2 - 10.1007/BF01762118

DO - 10.1007/BF01762118

M3 - Article

AN - SCOPUS:0023826478

SN - 0178-4617

VL - 3

SP - 279

EP - 288

JO - Algorithmica

JF - Algorithmica

IS - 1

ER -

Parallel triangulation of a polygon in two calls to the trapezoidal map

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this