INTERSECTION QUERIES IN CURVED OBJECTS

被引：17

作者：

AGARWAL, PK ^{[1
]}

VANKREVELD, M ^{[1
]}

OVERMARS, M ^{[1
]}

机构：

[1] UNIV UTRECHT,DEPT COMP SCI,3508 TB UTRECHT,NETHERLANDS

来源：

JOURNAL OF ALGORITHMS | 1993年 / 15卷 / 02期

关键词：

D O I：

10.1006/jagm.1993.1040

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A number of problems of the following type are studied: Given a set of n arcs (disks, circles, circular arcs, Jordan arcs) in the plane, preprocess it into a data structure, so that for a query line (or segment) one can quickly (i) report all arcs intersecting it, or (ii) count the number of arcs intersecting it. We also study the ray-shooting problem among disjoint Jordan arcs and circular arcs. Most of the data structures presented here use close to linear space and have query time close to O(√n + K) or O(n2/3 + K), where K is the size of the output. © 1993 Academic Press, Inc.

引用

页码：229 / 266

页数：38

共 41 条

[1] PARTITIONING ARRANGEMENTS OF LINES .2. APPLICATIONS [J].

AGARWAL, PK .

DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (06) :533-573

[2] RAY SHOOTING AND OTHER APPLICATIONS OF SPANNING-TREES WITH LOW STABBING NUMBER [J].

AGARWAL, PK .

SIAM JOURNAL ON COMPUTING, 1992, 21 (03) :540-570

[3] PARTITIONING ARRANGEMENTS OF LINES .1. AN EFFICIENT DETERMINISTIC ALGORITHM [J].

AGARWAL, PK .

DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (05) :449-483

[4] APPLICATIONS OF A NEW SPACE-PARTITIONING TECHNIQUE [J].

AGARWAL, PK ;

SHARIR, M .

DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 9 (01) :11-38

[5] SHARP UPPER AND LOWER BOUNDS ON THE LENGTH OF GENERAL DAVENPORT-SCHINZEL SEQUENCES [J].

AGARWAL, PK ;

SHARIR, M ;

SHOR, P .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1989, 52 (02) :228-274

[6]

AGGARWAL A, 1990, 21ST P ACM S THEOR C, P331

[7] THE POWER OF GEOMETRIC DUALITY [J].

CHAZELLE, B ;

GUIBAS, LJ ;

LEE, DT .

BIT, 1985, 25 (01) :76-90

[8] FILTERING SEARCH - A NEW APPROACH TO QUERY-ANSWERING [J].

CHAZELLE, B .

SIAM JOURNAL ON COMPUTING, 1986, 15 (03) :703-724

[9] QUASI-OPTIMAL RANGE SEARCHING IN SPACES OF FINITE VC-DIMENSION [J].

CHAZELLE, B ;

WELZL, E .

DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (05) :467-489

[10] QUASI-OPTIMAL UPPER-BOUNDS FOR SIMPLEX RANGE SEARCHING AND NEW ZONE THEOREMS [J].

CHAZELLE, B ;

SHARIR, M ;

WELZL, E .

ALGORITHMICA, 1992, 8 (5-6) :407-429

← 1 2 3 4 5 →