INTERSECTION AND CLOSEST-PAIR PROBLEMS FOR A SET OF PLANAR DISKS

被引：59

作者：

SHARIR, M ^{[1
]}

机构：

[1] NYU, COURANT INST MATH SCI, DEPT COMP SCI, NEW YORK, NY 10012 USA

来源：

SIAM JOURNAL ON COMPUTING | 1985年 / 14卷 / 02期

关键词：

D O I：

10.1137/0214034

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Efficient algorithms for detecting intersections and computing closest neighbors in a set of circular discs are presented and analyzed. They adapt known techniques for solving these problems for sets of points or of line segments. The main portion of the paper contains the construction of a generalized Voronoi diagram for a set of n (possibly intersecting) circular discs in time O(n log**2n), and its applications.

引用

页码：448 / 468

页数：21

共 12 条

[1]

BENTLEY JL, 1979, IEEE T COMPUT, V28, P643, DOI 10.1109/TC.1979.1675432

[2]

DRYSDALE RL, 1979, STANCS79705 STANF U

[3]

DRYSDALE RL, 1978, 16TH P ANN ALL C COM, P833

[4] EFFICIENT DETECTION OF INTERSECTIONS AMONG SPHERES [J].

HOPCROFT, JE ;

SCHWARTZ, JT ;

SHARIR, M .

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH, 1983, 2 (04) :77-80

[5] OPTIMAL SEARCH IN PLANAR SUBDIVISIONS [J].

KIRKPATRICK, D .

SIAM JOURNAL ON COMPUTING, 1983, 12 (01) :28-35

[6]

Kirkpatrick D. G., 1979, 20th Annual Symposium of Foundations of Computer Science, P18, DOI 10.1109/SFCS.1979.15

[7] GENERALIZATION OF VORONOI DIAGRAMS IN THE PLANE [J].

LEE, DT ;

DRYSDALE, RL .

SIAM JOURNAL ON COMPUTING, 1981, 10 (01) :73-87

[8] PLANE-SWEEP ALGORITHMS FOR INTERSECTING GEOMETRIC-FIGURES [J].

NIEVERGELT, J ;

PREPARATA, FP .

COMMUNICATIONS OF THE ACM, 1982, 25 (10) :739-747

[9] A NEW APPROACH TO PLANAR POINT LOCATION [J].

PREPARATA, FP .

SIAM JOURNAL ON COMPUTING, 1981, 10 (03) :473-482

[10] ON THE PIANO MOVERS PROBLEM .1. THE CASE OF A TWO-DIMENSIONAL RIGID POLYGONAL BODY MOVING AMIDST POLYGONAL BARRIERS [J].

SCHWARTZ, JT ;

SHARIR, M .

COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 1983, 36 (03) :345-398

← 1 2 →