Farthest-polygon Voronoi diagrams

被引：0

作者：

Cheong, Otfried ^{[1
]}

Everett, Hazel ^{[2
]}

Glisse, Marc ^{[3
]}

Gudmundsson, Joachim ^{[4
]}

Hornus, Samuel ^{[5
]}

Lazard, Sylvain ^{[5
]}

Lee, Mira ^{[1
]}

Na, Hyeon-Suk ^{[6
]}

机构：

[1] Korea Adv Inst Sci & Technol, Dept Comp Sci, Taejon 305701, South Korea

[2] Univ Nancy 2, LORIA, Nancy, France

[3] Inria Saclay Ile France, Orsay, France

[4] Natl ICT Australia Ltd, Sydney, NSW, Australia

[5] Inria Nancy Grand Est, LORIA, Nancy, France

[6] Soongsil Univ, Sch Comp, Seoul, South Korea

来源：

ALGORITHMS - ESA 2007, PROCEEDINGS | 2007年 / 4698卷

关键词：

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Given a family of k disjoint connected polygonal sites of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(n log(3) n) time algorithm to compute it.

引用

页码：407 / +

页数：2

共 14 条

[1] ABELLANAS M, 2001, 17 EUR WORKSH COMP G, P113
[2] Abellanas M., 2001, LNCS, V2161, P278
[3] [Anonymous], 2000, Geometry, Spinors and Applications
[4] Farthest line segment Voronoi diagrams
Aurenhammer, F.
Drysdale, R. L. S.
Krasser, H.
[J]. INFORMATION PROCESSING LETTERS, 2006, 100 (06) : 220 - 225
[5] Aurenhammer F, 2000, HANDBOOK OF COMPUTATIONAL GEOMETRY, P201, DOI 10.1016/B978-044482537-7/50006-1
[6] EDELSBRUNNER H, 1986, SIAM J COMPUTING, V15
[7] A SWEEPLINE ALGORITHM FOR VORONOI DIAGRAMS
FORTUNE, S
[J]. ALGORITHMICA, 1987, 2 (02) : 153 - 174
[8] THE UPPER ENVELOPE OF VORONOI SURFACES AND ITS APPLICATIONS
HUTTENLOCHER, DP
KEDEM, K
SHARIR, M
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 9 (03) : 267 - 291
[9] An optimal algorithm for the intersection radius of a set of convex polygons
Jadhav, S
Mukhopadhyay, A
Bhattacharya, B
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1996, 20 (02): : 244 - 267
[10] APPLYING PARALLEL COMPUTATION ALGORITHMS IN THE DESIGN OF SERIAL ALGORITHMS
MEGIDDO, N
[J]. JOURNAL OF THE ACM, 1983, 30 (04) : 852 - 865

← 1 2 →