講演名	1997/10/31 平面セグメントの上エンベロプを求める並列アルゴリズム 陳 慰, 和田 幸一,
PDFダウンロードページ	PDFダウンロードページへ
抄録(和)	平面セグメントの上エンベロプは点 (0, +∞) から見えるセグメントの各部分から構成され、構成されるセグメントの個数を上エンベロプのサイズと呼ぶ。エンベロプは可視性問題、アレンジメントの構成問題、移動計画問題などに多くの応用がある。本稿では平面セグメントの上エンベロプを求めるEREW PRAM上の並列解法を提案する。まず、n本の交差可能な線分の上エンベロプをO(log n) 時間、O(n) プロセッサで求める、n本の非交差線分の上エンベロプを、線分の端点がx座標によってソートティングされたとき、O(log n) 時間、O(n/log n) プロセッサで求める2つの最適アルゴリズムを示す。次に、一般的なn本のk-交差可能なセグメントの上エンベロプを、任意のε>0に対して、O(log^<1+ε>n) 時間、O(λ_(n)/log^εn) プロセッサで求めるアルゴリズムを示す。ただし、λ_(n) は上エンベロプのサイズである。さらに、我々の並列解法によって次のような逐次的な結果が得られる : 線分が勾配によって、そして線分の端点がx座標によってソーティングされたとき、n本の交差可能な線分の上エンベロプがO(n log log n) 時間で求められる。この結果はこの問題の既知の時間計算量の最小上界Θ(n log n) を改良した。
抄録(英)	We present parallel methods for finding the upper envelope of segments in the plane in the EREW PRAM. We give two optimal algorithms: finding the upper envelope of n possibly-intersecting line segments in O(log n) time using O(n) processors, and finding the upper envelope of n nonintersecting line segments whose endpoints are sorted in the x-coordinates in O(log n) time using O(n/log n) processors. More generally, we show that the upper envelope of n k-intersecting segments can be found in O(log^<1+ε>n) time using O(λ_(n)/log^εn) processors for any ε>0, where λ_(n) is the size of the upper envelope. Our parallel methods give an improved sequential result: if n possibly-intersecting line segments are sorted in increasing slope and their endpoints are sorted in increasing x-coordinate, their upper envelope can be found only in O(n log log n) time, but the best sequential algorithm for this problem by so far runs in Θ(n log n) time.
キーワード(和)	計算幾何学 / 並列アルゴリズム / PARAモデル / セグメントの上エンベロプ
キーワード(英)	computational geometry / parallel algorithms / PRAM model / the upper envelope of segments
資料番号	COMP97-49
発行日

研究会情報
研究会	COMP
開催期間	1997/10/31(から1日開催)
開催地（和）
開催地（英）
テーマ（和）
テーマ（英）
委員長氏名（和）
委員長氏名（英）
副委員長氏名（和）
副委員長氏名（英）
幹事氏名（和）
幹事氏名（英）
幹事補佐氏名（和）
幹事補佐氏名（英）

講演論文情報詳細
申込み研究会	Theoretical Foundations of Computing (COMP)
本文の言語	ENG
タイトル（和）	平面セグメントの上エンベロプを求める並列アルゴリズム
サブタイトル（和）
タイトル（英）	On Computing the Upper Envelope of Segments in Parallel
サブタイトル（和）
キーワード(1)（和/英）	計算幾何学 / computational geometry
キーワード(2)（和/英）	並列アルゴリズム / parallel algorithms
キーワード(3)（和/英）	PARAモデル / PRAM model
キーワード(4)（和/英）	セグメントの上エンベロプ / the upper envelope of segments
第 1 著者 氏名（和/英）	陳 慰 / Wei Chen
第 1 著者 所属（和/英）	名古屋工業大学電気情報工学科 Department of Electrical and Computer Engineering Nagoya Institute of Technology
第 2 著者 氏名（和/英）	和田 幸一 / Koichi Wada
第 2 著者 所属（和/英）	名古屋工業大学電気情報工学科 Department of Electrical and Computer Engineering Nagoya Institute of Technology
発表年月日	1997/10/31
資料番号	COMP97-49
巻番号（vol）	vol.97
号番号（no）	356
ページ範囲	pp.-
ページ数	8
発行日