Color Spanning Annulus: Square, Rectangle and Equilateral Triangle

2016/09/14 by Acharyya, Ankush, Nandy, Subhas C., Roy, Sasanka
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1609.04148

Abstract

In this paper, we study different variations of minimum width color-spanning annulus problem among a set of points P=\p₁,p₂,…,p_n\ in I R², where each point is assigned with a color in \1, 2, …, k\. We present algorithms for finding a minimum width color-spanning axis parallel square annulus (CSSA), minimum width color spanning axis parallel rectangular annulus (CSRA), and minimum width color-spanning equilateral triangular annulus of fixed orientation (CSETA). The time complexities of computing (i) a CSSA is O(n³+n²klog k) which is an improvement by a factor n over the existing result on this problem, (ii) that for a CSRA is O(n⁴log n), and for (iii) a CSETA is O(n³k). The space complexity of all the algorithms is O(k).

Related

• On the Minimum-Area Rectangular and Square Annulus Problem
• Maximum-Width Rainbow-Bisecting Empty Annulus
• Minimum-Width Double-Strip and Parallelogram Annulus
• Maximum-width Axis-Parallel Empty Rectangular Annulus
• Asymmetric Separation Problem for Bichromatic Point Set