Expected computations on color spanning sets
文献类型：期刊论文
| 作者 | Li Chao; Fan Chenglin; Luo Jun; Zhong Farong; Zhu Binhai |
| 刊名 | JOURNAL OF COMBINATORIAL OPTIMIZATION
 |
| 出版日期 | 2015 |
| 英文摘要 | Given a set of points, each is painted by one of the given colors, we want to choose points with distinct colors to form a color spanning set. For each color spanning set, we can construct the convex hull and the smallest axis-aligned enclosing rectangle, etc. Assuming that each point is chosen independently and identically from the subset of points of the same color, we propose an time algorithm to compute the expected area of convex hulls of the color spanning sets and an time algorithm to compute the expected perimeter of convex hulls of the color spanning sets. For the expected perimeter (resp. area) of the smallest perimeter (resp. area) axis-aligned enclosing rectangles of the color spanning sets, we present an (resp. ) time algorithm. We also propose a simple approximation algorithm to compute the expected diameter of the color spanning sets. For the expected distance of the closest pair, we show that it is P-complete to compute and there exists no polynomial time approximation algorithm to compute the probability that the closest pair distance of all color spanning sets equals to a given value unless , even in one dimension and when each color paints two points |
| 收录类别 | SCI |
| 原文出处 | http://link.springer.com/article/10.1007/s10878-014-9764-7 |
| 语种 | 英语 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/6876]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | JOURNAL OF COMBINATORIAL OPTIMIZATION |
| 推荐引用方式 GB/T 7714 | Li Chao,Fan Chenglin,Luo Jun,et al. Expected computations on color spanning sets[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,2015. |
| APA | Li Chao,Fan Chenglin,Luo Jun,Zhong Farong,&Zhu Binhai.(2015).Expected computations on color spanning sets.JOURNAL OF COMBINATORIAL OPTIMIZATION. |
| MLA | Li Chao,et al."Expected computations on color spanning sets".JOURNAL OF COMBINATORIAL OPTIMIZATION (2015). |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。