Memoirs of the Faculty of Engineering, Yamaguchi University

Back to Top
Permalink : https://petit.lib.yamaguchi-u.ac.jp/15057
Memoirs of the Faculty of Engineering, Yamaguchi University Volume 39 Issue 1
published_at 1988-10

A Parallel Algorithm for the Construction of Voronoi Diagrams

Voronoi diagram 構成のための並列アルゴリズム
Abe Tatsurou
Inoue Katsushi
Takanami Itsuo
Taniguchi Hiroshi
fulltext
738 KB
KJ00000156724.pdf
About This Article
Descriptions
This paper presents a new algorithm for the construction of Voronoi diagrams on a shared memory parallel computer, where both concurrent reads and concurrent writes are allowed, but all the processors that simultaneously try to write in the same memory cell must write the same value. The algorithm is a parallel version of the sequential algorithm (for the construction of Voronoi diagrams) of Shamos and Hoey. The algorithm, for n input points, runs in O ((log)^3n) time with only n processors.
Other Article
Turbulence Properties of the Boundary Layer Over a d-type Rough Surface at a Low Reynoleds Number
PP. 1 - 6
On the Mechanism of Origin of the Non-uniformity in the Film-Cooling Process : 1st Report, Fundamental Properties of the Plane Wall Jet in the Self-Preserving State and Performance of the Experimental Equipment
PP. 7 - 15
Structure of the Blood Flow in the Vascular with Rough Wall
PP. 17 - 25
Tosinal Vibrasion of Marine Propulsion Shafting System Containing Generator
PP. 27 - 36
Dynamic Behavior of Differential Gears : Torque Variation and Effect of Tooth Bearing
PP. 37 - 46
Determination of Cutting Force by Photo-Elastic Coating Method
PP. 47 - 51
On the Machine Designing by Use of a Personal Computer, the M-Draf 16 with its 2-D CAD System
PP. 53 - 64
Measurement of Granular Surface Pattern in a Hopper by Ultrasnic Sensor (The 3rd Report)
PP. 65 - 71
A Human-Factors Analysis for Systems Supervision
PP. 73 - 81
Variations of Fracture Strength, Crack Velocity and Fracture Surface Marks due to the Design of a Single Edge Notched Tensile Specimen : In the Case of Unsaturated Polyester Resin
PP. 83 - 92
Theoretical Analysis of the Vibration in an Industrial Robot due to a Strain Wave Gearing
PP. 93 - 100
Study of a Packed Bed Dust Collector : Dust Collection Characteristics Inside the Bed in a Fixed Bed
PP. 101 - 110
An Experimental Study on Generation Mechanism of Combustion Induced Engine Noise : 3rd Report; Noise Radiation from Engine Walls
PP. 111 - 117
Pressure Fluctuation Model of Fluidized Bed
PP. 119 - 125
Synthesis and Thermostabilities of N-Substituted Maleimide Copolymers. I : N-Cyclohexylmaleimide Copolymers
PP. 127 - 133
Synthesis and Thermostabilities of N-Substituted Maleimide Copolymers. II : N-Benzylmaleimide Copolymers
PP. 135 - 141
Ring-opening Reaction of 2,2-Dichloro-1'-methyl-spiro [cyclopropane-1,9'-fluorene] Derivatives
PP. 143 - 148
On the 1987 Yamaguchiken-Chube Earthquake (M=5.2)
PP. 149 - 158
Evaluation of Stresses in Saturated Sand Deposit Subjected to Traffic Loads
PP. 159 - 167
Analysis of Running Characteristics of Motorcycles : 1st Report, Equation of Motion with Finite Displacements
PP. 169 - 175
On the Delay-Minimizing Offsets Based on the Rectangular Platon Model
PP. 177 - 188
An Experimental and Analytical Study on Ultimate Strength of Thin-Walled Curved Box Girders
PP. 189 - 194
The Relationship Between the Seismicity and the Consciousness of Earthquake Disaster Prevention in Schools
PP. 195 - 203
Numerical Simulation for Response of vibration Level Meter
PP. 205 - 211
A Posteriori Probability Density of System Described by Fanctional Expansion
PP. 213 - 224
A Parallel Algorithm for the Construction of Voronoi Diagrams
PP. 225 - 233
On Two Criteria for Fingerprint Image Quality
PP. 235 - 242
Magneto-Optical Properties of Impurity-Doped PtMnSb Films
PP. 243 - 250
Analyses of Glutamate Current Fluctuations and Glutamate Single Channel Currents of Cultured Brain Neurons
PP. 251 - 257