Effiiently computing the smallest axis-parallel squares spanning all colors

Document Type : Article

Authors

1 Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran.

2 716 CE Building, Sharif University of Technology, Tehran, Iran.

3 Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

4 3204 A.V. Williams Building, University of Maryland, College Park, Maryland, USA

Abstract

For a set of colored points, a region is called color-spanning if it contains at least one point of each color. In this paper, we rst consider the problem of maintaining the smallest color-spanning interval for a set of n points with k colors on the real line, such that the insertion and deletion of an arbitrary point takes O(log2 n) the worst-case time. Then, we exploit the data structure to show that there is O(n log2 n) time algorithm to
compute the smallest color-spanning square for a set of n points with k colors in the plane. This is a new way to improve O(nk log n) time algorithm presented by Abellanas et al. [1] when k = !(log n). We also consider the problem of computing the smallest color-spanning square in a special case in which we have, at most, two points from each color. We present O(n log n) time algorithm to solve the problem which improves the result presented by Arkin et al. [2] by a factor of log n.

Keywords

Main Subjects

Scientia Iranica
Volume 24, Issue 3
Transactions on Computer Science & Engineering and Electrical Engineering (D)
May and June 2017
Pages 1325-1334

Files

History

  • Receive Date: 12 November 2015
  • Revise Date: 22 August 2016
  • Accept Date: 19 December 2016

Share

How to cite

Statistics