A Parallel Method for the Prefix Convex Hulls Problem
スポンサーリンク
概要
- 論文の詳細を見る
Given a sorted set S of n points in the plane, the prefix convex hulls problem of S is to compute the convex hull for every prefix set of S. We present a parallel algorithm for this problem. Our algorithm runs in O(log n) time using n/log n processors in the CREW PRAM computational model. The algorithm is shown to be time and cost optimal. One of the techniques we adopt to achieve these optimal bounds is the use of a new parallel data structure Array-Tree.
- 社団法人電子情報通信学会の論文
- 1994-10-25
著者
-
Chen Wei
Department of Obstetrics and Gynecology, Kobe University Graduate School of Medicine
-
Nakano K
School Of Information Science Japan Advanced Institute Of Technology
-
MASUZAWA Toshimitsu
the Graduate School of Information Science and Technology, Osaka University
-
Masuzawa Toshimitsu
Graduate School Of Information Science Nara Institute Of Science And Technology
-
Masuzawa Toshimitsu
Nara Institute Of Sciences And Technology
-
Masuzawa Toshimitsu
Department Of Computer Science Graduate School Of Information Science And Technology Osaka Universit
-
Nakano Koji
Advanced Research Laboratory Hitachi Ltd.
-
Tokura Nobuki
Faculty of Engineering Science, Osaka University
-
Nakano Koji
The Department Of Electrical And Computer Engineering Nagoya Institute Of Technology
-
Tokura N
Department Of Informatics And Mathematical Science Graduate School Of Enginnering Science Osaka Univ
-
Tokura Nobuki
Faculty Of Engineering Science Osaka University
-
Chen Wei
Department Of Food And Nutrition Providence University
-
Chen Wei
Department Of Electrical And Computer Engineering Nagoya Institute Of Technology
-
Chen Wei
Department Of Chemical Engineering Nagoya University
-
Chen Wei
Department of Cell Biology, Third Military Medical University
関連論文
- Fault-Tolerant and Self-Stabilizing Protocols Using an Unreliable Failure Detector
- Effects of progesterone receptor modulator CDB2914 on apoptosis of cultured uterine leiomyoma cells(Oncology 12)
- 7-24.Direct Effects of GnRH Antagonist (Cetrorelix) on Proliferative Activity, Apoptosis and EGF Expression in Cultured Human Uterine Leiomyoma Cells(Session 9 Others 1)
- Magnetization plateaus in one dimensional S=1/2 Heisenberg model with dimerization and quadrumerization
- Ground State Properties of One Dimensional S=1/2 Heisenberg Model with Dimerization and Quadrumerization
- Fundamental Protocols to Gather Information in Wireless Sensor Networks(Regular Section)
- An Energy-Efficient Initialization Protocol for Wireless Sensor Networks with No Collision Detection
- Energy-Efficient Initialization Protocols for Ad-Hoc Radio Networks
- Timed Uniform Atomic Broadcast in Presence of Crash and Timing Faults(Foundations of Computer Science)
- SAGE library screening reveals ILT7 as a specific plasmacytoid dendritic cell marker that regulates type I IFN production
- Wait-Free Linearizable Distributed Shared Memory
- Parallel Algorithms for the All Nearest Neighbors of Binary Image on the BSP Model
- High-Level Synthesis for Weakly Testable Data Paths(Special Issue on Test and Diagnosis of VLSI)
- A Simple Parallel Algorithm for the Medial Axis Transform (Special Issue on Architectures Algorithms and Networks for Massively parallel Computing)
- Critical Properties of Spin-1 Antiferromagnetic Heisenberg Chains with Bond Alternation and Uniaxial Single-Ion-Type Anisotropy
- Bond operator mean field approach to the magnetization plateaux in quantum antiferromagnets - Application to the S=1/2 coupled dimerized zigzag Heisenberg chains
- Magnetization plateaus in antiferromagnetic-(ferromagnetic), polymerized S=1/2 XXZ chains
- Ground State Phase Diagram of the One Dimensional S=1/2 XXZ Model with Dimerization and Quadrumerization
- Hand-assisted versus pure laparoscopic radical cystectomy : A clinical outcome comparison
- Hand-assisted laparoscopic radical cystectomy and extracorporeal urinary diversion : Experience with 31 cases
- Enzymatic Conversion of Dehydrodivanillin to Vanillin by an Anaerobic Recombinant FE7
- Anaerobic Degradation of Dehydrodiisoeugenol by Rumen Bacteria
- A Parallel Method for the Prefix Convex Hulls Problem
- Distributed Leader Election on Chordal Ring Networks
- Simultaneous Voltammetric Determination of Ascorbic Acid, Dopamine and Uric Acid Using Polybromothymol Blue Film-Modified Glassy Carbon Electrode
- A Polymer Film Modified Sensor for Voltammetric Determination of Uric Acid in the Presence of Ascorbic Acid and Its Application in Urine
- LATERAL AND AXIAL MIXING OF THE DISPERSED PARTICLES IN CFB
- Polynomially Fast Parallel Algorithms for Some P-Complete Problems (Special Section on Discrete Mathematics and Its Applications)
- Parallel Algorithms for Convex Hull Problems and Their Paradigm(Special Issue on Algorithm Engineering : Surveys)
- Scheduling for Independent-Task Applications on Heterogeneous Parallel Computing Environments under the Unidirectional One-Port Model(Parallel and Distributed Computing,Foundations of Computer Science)
- Scheduling for Gather Operation in Heterogeneous Parallel Computing Environments
- Doubly-Logarithmic Energy-Efficient Initialization Protocols for Single-Hop Radio Networks(Special Section on Discrete Mathematics and Its Applications)
- Molecular phylogeny of species in the genera Amylostereum and Echinodontium
- A Self-Stabilizing Spanning Tree Protocol that Tolerates Non-quiescent Permanent Faults
- A Language for System Programs and Its Implementation Using a Macro Processor
- Therapeutic potential and related signal pathway of adipose-derived stem cell transplantation for rat liver injury
- Effects of Xylooligosaccharides in Type 2 Diabetes Mellitus
- Fault-Tolerance of Distributed Algorithms : Self-Stabilization and Wait-Freedom(Special Issue on Algorithm Engineering : Surveys)
- A Non-scan DFT Method at Register-Transfer Level to Achieve 100% Fault Efficiency (特集:システムLSIの設計技術と設計自動化)
- Parallel Selection Algorithms for CGM and BSP Models with Application to Sorting (特集 並列処理) -- (並列・分散アルゴリズム)
- Efficient Linearizable Implementation of Shared FIFO Queues and General Objects on a Distributed System(Special Section on Discrete Mathematics and Its Applications)
- Alternative lengthening of telomeres in hTERT-inhibited laryngeal cancer cells
- Content of Selected Flavonoids in 100 Edible Vegetables and Fruits
- Band-Bending at the Graphene–SiC Interfaces: Effect of the Substrate
- Simulating a Mesh with Separable Buses
- Designing Efficient Parallel Algorithms with Multi-Level Divide-and-Conquer (Special Section on Discrete Mathematics and Its Applications)
- Renormalization Group Potential for Quasi-One-Dimensional Correlated Systems(Yukawa International Seminar 2004 (YKIS2004) Physics of Strongly Correlated Electron Systems)
- Finding the Envelope of Segments in Parallel
- Low-Temperature Growth of SiO_2 Films by Electron-Induced Ultrahigh Vacuum Chemical Vapor Deposition
- Electrochemical Oxidation of Luteolin at a Glassy Carbon Electrode and Its Application in Pharmaceutical Analysis
- Derivation of Hepatocytes From Injected Bone Marrow cells in Mice After Partia Hepatectomy and D-Galactosamine Induced Hepatic Injury(THE SIXTH JAPAN-CHINA JOINT SEMINAR ON HISTOCHEMISTRY AND CYTOCHEMISTRY)
- An Efficient Algorithm for Summing up Binary Values on a Reconfigurable Mesh (Special Section on Discrete Mathematics and Its Applications)
- Characterization of Rat Hair Follicle Stem Cells Selected by Vario Magnetic Activated Cell Sorting System
- Establishment of an Experimental Mouse Model of Trauma-Hemorrhagic Shock
- A Leakage-Aware CS/CB Scheme for Heterogeneous CoMP Networks with Layered Limited Feedback
- A fuzzy evaluation of schedule robustness under processing time variations in batch plants.
- Effect of the regulation of retinoid X receptor-α gene expression on rat hepatic fibrosis