Expected computations on color spanning sets

• DOI: 10.1007/s10878-014-9764-7
• Publication Date: 2014-06-19T08:22:52Z
• Authors: Chao Li; Chenglin Fan; Jun Luo; Farong Zhong; Binhai Zhu
• Keywords: 0102 computer and information sciences; 01 natural sciences

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.