An optimal parallel algorithm for the visibility of a simple polygon from a point
Copyright policy )An optimal parallel algorithm for the visibility of a simple polygon from a point
Summary: We present a parallel algorithm for computing the visible portion of a simple polygonal chain with \(n\) vertices from a point in the plane. The algorithm runs in \(O(\log n)\) time using \(O(n/\log n)\) processors in the CREW-PRAM computational model, and hence is asymptotically optimal.
- Purdue University System United States
- Purdue University Northwest United States
- Purdue University
- Purdue University
- Purdue University West Lafayette United States
Computer Sciences, Analysis of algorithms and problem complexity, visible regions, Computer graphics; computational geometry (digital and algorithmic aspects), computational geometry, simple polygons, parallel computational complexity, intersections of polygonal chains
Computer Sciences, Analysis of algorithms and problem complexity, visible regions, Computer graphics; computational geometry (digital and algorithmic aspects), computational geometry, simple polygons, parallel computational complexity, intersections of polygonal chains
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).14 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!