TRIANGULATING DISJOINT JORDAN CHAINS

被引:43
作者
Bar-Yehuda, Reuven [1 ]
Chazelle, Bernard [2 ]
机构
[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel
[2] Princeton Univ, Dept Comp Sci, Princeton, NJ 08544 USA
关键词
Simple polygon; triangulation; trapezoidal decomposition; visibility map; Jordan curves;
D O I
10.1142/S0218195994000252
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Recent advances on polygon triangulation have yielded efficient algorithms for a large number of problems dealing with a single simple polygon. If the input consists of several disjoint polygons, however, it is often desirable to merge them in preprocessing so as to produce a single polygon that retains the geometric characteristics of its individual components. We give an efficient method for doing so, which combines a generalized form of Jordan sorting with the efficient use of point location and interval trees. As a corollary, we are able to triangulate a collection of p disjoint Jordan polygonal chains in time O(n+p(log p)(1+epsilon)), for any fixed epsilon > 0, where n is the total number of vertices. A variant of the algorithm gives a running time of O((n + p log p) log log p). The performance of these solutions approaches the lower bound of Omega(n p log p).
引用
收藏
页码:475 / 481
页数:7
相关论文
共 14 条
[1]   TRIANGULATING A SIMPLE POLYGON IN LINEAR TIME [J].
CHAZELLE, B .
DISCRETE & COMPUTATIONAL GEOMETRY, 1991, 6 (05) :485-524
[2]   TRIANGULATION AND SHAPE-COMPLEXITY [J].
CHAZELLE, B ;
INCERPI, J .
ACM TRANSACTIONS ON GRAPHICS, 1984, 3 (02) :135-152
[3]  
Clarkson K., 1989, DISCRETE COMPUT GEOM, V4, P432
[4]   OPTIMAL POINT LOCATION IN A MONOTONE SUBDIVISION [J].
EDELSBRUNNER, H ;
GUIBAS, LJ ;
STOLFI, J .
SIAM JOURNAL ON COMPUTING, 1986, 15 (02) :317-340
[5]   TRIANGULATING SIMPLE POLYGONS AND EQUIVALENT PROBLEMS [J].
FOURNIER, A ;
MONTUNO, DY .
ACM TRANSACTIONS ON GRAPHICS, 1984, 3 (02) :153-174
[6]   TRIANGULATING A SIMPLE POLYGON [J].
GAREY, MR ;
JOHNSON, DS ;
PREPARATA, FP ;
TARJAN, RE .
INFORMATION PROCESSING LETTERS, 1978, 7 (04) :175-179
[7]   LINEAR-TIME ALGORITHMS FOR VISIBILITY AND SHORTEST-PATH PROBLEMS INSIDE TRIANGULATED SIMPLE POLYGONS [J].
GUIBAS, L ;
HERSHBERGER, J ;
LEVEN, D ;
SHARIR, M ;
TARJAN, RE .
ALGORITHMICA, 1987, 2 (02) :209-233
[8]  
HERTEL S, 1983, LECT NOTES COMPUT SC, V158, P207
[9]   SORTING JORDAN SEQUENCES IN LINEAR TIME USING LEVEL-LINKED SEARCH-TREES [J].
HOFFMANN, K ;
MEHLHORN, K ;
ROSENSTIEHL, P ;
TARJAN, RE .
INFORMATION AND CONTROL, 1986, 68 (1-3) :170-184
[10]   OPTIMAL SEARCH IN PLANAR SUBDIVISIONS [J].
KIRKPATRICK, D .
SIAM JOURNAL ON COMPUTING, 1983, 12 (01) :28-35