COUNTING CIRCULAR-ARC INTERSECTIONS

被引：14

作者：

AGARWAL, PK

PELLEGRINI, M

SHARIR, M

机构：

[1] RUTGERS UNIV,CTR DISCRETE MACHEMAT & THEORET COMP SCI,NEW BRUNSWICK,NJ 08903

[2] TEL AVIV UNIV,SCH MATH SCI,IL-69978 TEL AVIV,ISRAEL

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

[4] UNIV LONDON KINGS COLL,DEPT COMP SCI,LONDON WC2R 2LS,ENGLAND

来源：

SIAM JOURNAL ON COMPUTING | 1993年 / 22卷 / 04期

关键词：

ARRANGEMENTS; POINT LOCATION; RANDOM SAMPLING; PARTITION TREE;

D O I：

10.1137/0222050

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper efficient algorithms for counting intersections in a collection of circles or circular arcs are presented. An algorithm for counting intersections in a collection of n circles is presented whose running time is O(n3/2+epsilon), for any epsilon > 0 is presented. Using this algorithm as a subroutine, it is shown that the intersections in a set of n circular arcs can also be counted in time O(n3/2+epsilon). If all arcs have the same radius, the running time can be improved to O(n4/3+epsilon), for any epsilon > 0.

引用

页码：778 / 793

页数：16

共 23 条

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