PARTITIONING ARRANGEMENTS OF LINES .1. AN EFFICIENT DETERMINISTIC ALGORITHM

被引：33

作者：

AGARWAL, PK ^{[1
]}

机构：

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

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1990年 / 5卷 / 05期

关键词：

D O I：

10.1007/BF02187805

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we consider the following problem: Given a set ℒ of n lines in the plane, partition the plane into O(r2) triangles so that no triangle meets more than O(n/r) lines of ℒ. We present a deterministic algorithm for this problem with O(nr log n/r) running time, where ω is a constant <3.33. © 1990 Springer-Verlag New York Inc.

引用

页码：449 / 483

页数：35

共 25 条

[1] PARTITIONING ARRANGEMENTS OF LINES .2. APPLICATIONS
AGARWAL, PK
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (06) : 533 - 573
[2] RED-BLUE INTERSECTION DETECTION ALGORITHMS, WITH APPLICATIONS TO MOTION PLANNING AND COLLISION DETECTION
AGARWAL, PK
SHARIR, M
[J]. SIAM JOURNAL ON COMPUTING, 1990, 19 (02) : 297 - 321
[3] [Anonymous], 1987, EATCS MONOGRAPHS THE
[4] Chazelle B., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P539, DOI 10.1109/SFCS.1988.21970
[5] CLARKSON, 1988, 4TH P ANN S COMP GEO, P1
[6] CLARKSON K, 1985, 17TH P ACM S THEOR C, P75
[7] CLARKSON K, 1987, DISCRETE COMPUTATION, P195
[8] A FAST LAS-VEGAS ALGORITHM FOR TRIANGULATING A SIMPLE POLYGON
CLARKSON, KL
TARJAN, RE
VANWYK, CJ
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (05) : 423 - 432
[9] CLARKSON KL, 1988, 4TH P ACM S COMP GEO, P12
[10] ON K-HULLS AND RELATED PROBLEMS
COLE, R
SHARIR, M
YAP, CK
[J]. SIAM JOURNAL ON COMPUTING, 1987, 16 (01) : 61 - 77

← 1 2 3 →