# Spanning Colored Points with Intervals

@inproceedings{Khanteimouri2013SpanningCP, title={Spanning Colored Points with Intervals}, author={Payam Khanteimouri and Ali Mohades and Mohammad Ali Abam and Mohammad Reza Kazemi}, booktitle={CCCG}, year={2013} }

We study a variant of the problem of spanning colored objects where the goal is to span colored objects with two similar regions. We dedicate our attention in this paper to the case where objects are points lying on the real line and regions are intervals. Precisely, the goal is to compute two intervals together spanning all colors. As the main ingredient of our algorithm, we first introduce a kinetic data structure to keep track of minimal intervals spanning all colors. Then we present a novel… Expand

#### 6 Citations

Shortest color-spanning intervals

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2016

An improved algorithm with running time of O ( n 2 ) for SCSI-2 with arbitrary s i ≥ 1 with fixed-parameter tractable with k as the parameter is presented and admits an exact algorithm running in O ( 2 k n ⋅ max { k, log n } ) time. Expand

Color Spanning Objects: Algorithms and Hardness Results

- Mathematics, Computer Science
- CALDAM
- 2016

Given that the problem turns out to be W[1]-hard parameterized by the standard parameters, a new parameter is introduced, namely sparsity, and new hardness and tractability results are proved in this context. Expand

Shortest Color-Spanning Intervals

- Mathematics, Computer Science
- COCOON
- 2014

An improved algorithm with running time of O(n 2) for SCSI-2 with arbitrary s i ≥ 1 with fixed-parameter tractable with k as the parameter is presented and admits an exact algorithm running in O(2 k n· max {k,logn}) time. Expand

Efficiently approximating color-spanning balls

- Mathematics, Computer Science
- Theor. Comput. Sci.
- 2016

It is demonstrated that for any e 0 under the assumption that SETH is true, no approximation algorithm running in O ( n 2 - e ) time exists for the problem even in one-dimensional space. Expand

Localized Query: Color Spanning Variations

- Computer Science, Mathematics
- CALDAM
- 2019

This paper presents efficient algorithms to pre-process P such that for a given query point q, it can quickly identify the smallest color spanning object of the desired type containing q. Expand

Color spanning Localized query

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2021

This paper presents efficient algorithms to pre-process P such that for a given query point q, it can quickly identify the smallest color spanning object of the desired type containing q. Expand

#### References

SHOWING 1-10 OF 13 REFERENCES

Smallest Color-Spanning Object Revisited

- Mathematics, Computer Science
- Int. J. Comput. Geom. Appl.
- 2009

A dynamic version of the problem is studied, where new points may be added, and the narrowest color-spanning corridor at any instance can be reported in O(mn(α(n))2log m) time. Expand

On some geometric problems of color-spanning sets

- Mathematics, Computer Science
- J. Comb. Optim.
- 2013

This paper proposes an O(n1+ε) time algorithm for the maximum diameter color-spanning set problem where ε could be an arbitrarily small positive constant and proposes two efficient constant factor approximation algorithms for the planar smallest perimeter color- spanning convex hull problem. Expand

Algorithms for Interval Structures with Applications

- Mathematics, Computer Science
- FAW-AAIM
- 2011

We present new algorithms for two problems on interval structures that arise in computer-aided manufacturing and in other areas. We give an O(Kn) time algorithm for the single-source K-link shortest… Expand

The Farthest Color Voronoi Diagram and Related Problems

- Mathematics, Computer Science
- 2001

This paper provides algorithms that may help to achieve this goal for various specifications of the term “neighborhood” for various types of facilities modeled by n colored points in the plane, each type by its own color. Expand

The upper envelope of Voronoi surfaces and its applications

- Computer Science, Mathematics
- SCG '91
- 1991

Borders on the number of vertices on the upper envelope of a collection of Voronoi surfaces are derived, and efficient algorithms to calculate these vertices are provided. Expand

On Enclosing k Points by a Circle

- Mathematics, Computer Science
- Inf. Process. Lett.
- 1995

This paper presents randomized algorithms for finding a smallest circle enclosing at least k points of P in the plane and an integer k ⩽ n, which improves on previous results by logarithmic factors. Expand

Further Results on Generalized Intersection Searching Problems: Counting, Reporting, and Dynamization

- Mathematics, Computer Science
- J. Algorithms
- 1995

A uniform framework is presented to solve efficiently the counting/reporting/dynamic versions of a variety of generalized intersection searching problems, including: 1-, 2-, and 3-dimensional range searching, quadrant searching, and 2-dimensional point enclosure searching. Expand

Finding k points with a smallest enclosing square

- Mathematics
- 1993

An algorithm is presented that, given a set of n points in the plane and an integer k, 2 ≤ k ≤ n, finds k points with a smallest enclosing axes-parallel square. The algorithm has a running time of… Expand

Kinetic Data Structures

- Computer Science, Mathematics
- Handbook of Data Structures and Applications
- 2004

A new type of data structure is created, called a kinetic data structure, made of a proof of correctness of the attribute which is animated through time by a discrete event simulation. Expand

Smallest Color-Spanning Objects

- Mathematics, Computer Science
- ESA
- 2001

This paper shows for a set of colored point sites in the plane how to compute the smallest-- by perimeter or area--axis-parallel rectangle and the narrowest strip enclosing at least one site of each color. Expand