THE EXPECTED SIZE OF THE SPHERE-OF-INFLUENCE GRAPH

被引：9

作者：

DWYER, RA ^{[1
]}

机构：

[1] N CAROLINA STATE UNIV,DEPT COMP SCI,RALEIGH,NC 27695

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1995年 / 5卷 / 03期

关键词：

D O I：

10.1016/0925-7721(94)00025-Q

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The sphere-of-influence graph of a set of point sites in R(d) is constructed by identifying the nearest neighbor of each site, centering a ball at each site so that its nearest neighbor lies on the boundary, and joining two sites by an edge if and only if their balls intersect. The asymptotic behavior of the expected number of edges of this graph is investigated when the sites are independent and uniformly distributed and their number grows without bound.

引用

页码：155 / 164

页数：10

共 11 条

[1]

BANERJIA S, 1993, THESIS N CAROLINA ST

[2] OPTIMAL EXPECTED-TIME ALGORITHMS FOR CLOSEST POINT PROBLEMS [J].

BENTLEY, JL ;

WEIDE, BW ;

YAO, AC .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1980, 6 (04) :563-580

[3] THE EXPECTED SIZE OF SOME GRAPHS IN COMPUTATIONAL GEOMETRY [J].

DEVROYE, L .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1988, 15 (01) :53-64

[4]

DWYER R, 1993, TR9321 N CAR STAT U

[5]

DWYER RA, 1994, UNPUB OPTIMAL ALGORI

[6] MULTIVARIATE GENERALIZATIONS OF THE WALD-WOLFOWITZ AND SMIRNOV 2-SAMPLE TESTS [J].

FRIEDMAN, JH ;

RAFSKY, LC .

ANNALS OF STATISTICS, 1979, 7 (04) :697-717

[7] RELATIVE NEIGHBORHOOD GRAPHS AND THEIR RELATIVES [J].

JAROMCZYK, JW ;

TOUSSAINT, GT .

PROCEEDINGS OF THE IEEE, 1992, 80 (09) :1502-1517

[8]

MICHAEL TS, 1994, UNPUB SPHERE OF INFL

[9]

REIFENBERG ER, 1948, MATH GAZ, V32, P290

[10]

Toussaint G. T., 1988, COMPUTATIONAL MORPHO, P229

← 1 2 →