Expected computations on color spanning sets

Chao Li (), Chenglin Fan (), Jun Luo (), Farong Zhong () and Binhai Zhu ()
Additional contact information
Chao Li: Chinese Academy of Sciences
Chenglin Fan: Chinese Academy of Sciences
Jun Luo: Chinese Academy of Sciences
Farong Zhong: Zhejiang Normal University
Binhai Zhu: Montana State University

Journal of Combinatorial Optimization, 2015, vol. 29, issue 3, No 5, 589-604

Abstract: Abstract Given a set of $$n$$ n points, each is painted by one of the $$k$$ k given colors, we want to choose $$k$$ k 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 $$O(n^2)$$ O ( n 2 ) time algorithm to compute the expected area of convex hulls of the color spanning sets and an $$O(n^2)$$ O ( n 2 ) 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(n\log n)$$ O ( n log n ) (resp. $$O(n^2)$$ O ( n 2 ) ) 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 $$2^{n^{1-\varepsilon }}$$ 2 n 1 - ε approximation algorithm to compute the probability that the closest pair distance of all color spanning sets equals to a given value $$d$$ d unless $$P=NP$$ P = N P , even in one dimension and when each color paints two points.

Keywords: Expected value; Imprecise data; Computational geometry (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9764-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:3:d:10.1007_s10878-014-9764-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9764-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().