AN OPTIMAL ALGORITHM FOR THE MAXIMUM 3-CHAIN PROBLEM

作     者：LOU, RD SARRAFZADEH, M 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1993年第22卷第5期

页      面：976-993页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：POINT DOMINANCE CHAINS COMPUTATIONAL GEOMETRY LOWER BOUND OPTIMAL ALGORITHM 

摘      要：Given a two-dimensional point set rho, a chain C is a subset of rho in which for every two points one is dominated by the other. A k-chain is a subset of rho that can be partitioned into k-chains. The size of a k-chain is the total number of its points. A k-chain with maximum size, among all possible k-chains, is called a maximum k-chain. First geometric properties of k-chains are studied for an arbitrary k. Then a THETA(n log n)-time algorithm is presented for finding a maximum three-chain in a point set rho, where n = Absolute value of rho.