Shortest Rectilinear Paths among Weighted Rectangles
スポンサーリンク
概要
- 論文の詳細を見る
We consider the problem of a rectilinear shortest path among weighted obstacles. Instead of restricting a path to avoid obstacles totally, we allow it to pass through them at, extra costs. The extra costs are represented by the weights of the obstacles. We aim to find a shortest rectilinear path between two distinguished points among a set of disjoint, weighted rectangles. By using a plane sweep approach and a data structure called the weighted segment tree, we obtain an algorithm that runs in optimalθ(n log n) time andθ(n) space, where n is the number of rectangles.
- 一般社団法人情報処理学会の論文
- 1991-02-10
著者
-
Lee D.
Department Of Cytokine Biology The Forsyth Institute
-
YANG C.
Department of Physics and Electron Spin Science Center, Pohang University of Science and Technology
-
Chen T.
Department Of Electrical Engineering And Computer Science Northwestern University
-
Yang C.
Department Of Civil Engineering National Chiao Tung University
関連論文
- Oxygen Diffusion in Single Sludge Floc
- Decreased Mineral Content in MMP-20 Null Mouse Enamel is Prominent During the Maturation Stage
- Simultaneous ground-based and satellite observations of Pc5 geomagnetic pulsations : A case study using multipoint measurements
- High Resolution Neutron Powder Diffraction and Elastic Constant Measurements of La_Ca_MnO_3 at High Temperatures(Condensed Matter : Structure, Mechanical and Thermal Properties)
- Robust Molten Steel Level Control in a Strip-casting Process
- LPE-Garnet Base Magneto-Optic Spatial Light Modulator
- FACTORS AFFECTING THE FIRST RECURRENCE OF NON-CARDIOEMBOLIC ISCHEMIC STROKE
- Effects of Ion Irradiation on Exchange Bias and GMR
- High Temperature Oxidation of TiAl/SiC_p Composites Manufactured by MA-SPS Process
- Shortest Rectilinear Paths among Weighted Rectangles
- 112 Development of a Sub-pixel Optical Vision System for Precision Tool Setting
- Behavioral Side Effects of Gabapentin in Children
- ENHANCED EFFICIENCY ON THE PARAMETERS ESTIMATION OF MUSKINGUM MODEL USING ARTIFICIAL NEURAL NETWORK
- OPTIMIZING THE RULE CURVES FOR MULTI-RESERVOIR OPERATIONS USING A GENETIC ALGORITHM AND HEC-5
- Modulation of the expression of HLA-DR and CD54 on monocytes by peritoneal fluid from endometriosis patients(Reproduction 6)
- New colonoscopy simulator with improved haptic fidelity
- Organic Thin-Film Transistors Based on Vapor-Deposition Polymerized Gate Insulators
- A New Period-Doubled Modulation on the In/Si(111)$4 \times 1$ Surface Induced by Defects
- Lung Transplantation in Patients with Pulmonary Emphysema
- Effect of Sn on the Superconductivity of the DyBa2Cu3O7-δ System
- Effects of Carbon Content and Thermo-Mechanical Treatment on Fe_Mn_Si_6Cr_5C_X (X = 0.015-0.1mass%) Shape Memory Alloys