Expected Computations on Color Spanning Sets
文献类型：会议论文
| 作者 | Fan, Chenglin; Luo, Jun; Zhong farong; Zhu, Binhai |
| 出版日期 | 2013 |
| 会议名称 | 7th International Frontiers in Algorithmics Workshop and the 9th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2013 |
| 会议地点 | Dalian , China |
| 英文摘要 | Given a set of n points, each is painted by one of the k given colors, we want to choose k points with distinct colors to form a color spanning set. For each colorspanning set, we can construct the convex hull and the smallest axis-aligned enclosing rectangle, etc. Assume that each point is chosen independently and identically from the subset of points of the same color, we propose an O(n 2logn) time algorithm to compute the expected area of convex hulls of the color spanningsets and an O(n 2logn) 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 O(nlogn) (resp. O(n 2)) time algorithm. We also propose an approximation algorithm to compute the expected diameter of the color spanning sets. © 2013 Springer-Verlag Berlin Heidelberg.(25 refs) |
| 收录类别 | EI |
| 语种 | 英语 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/5137]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | 2013 |
| 推荐引用方式 GB/T 7714 | Fan, Chenglin,Luo, Jun,Zhong farong,et al. Expected Computations on Color Spanning Sets[C]. 见:7th International Frontiers in Algorithmics Workshop and the 9th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2013. Dalian , China. |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。