Algorithms on Clustering, Orienteering, and Conflict -Free Coloring

In the last part, we present randomized algorithms for online conflict-free coloring of points in the plane, with respect to intervals, halfplanes, congruent disks, and nearly-equal axis-parallel rectangles. In all these cases, the coloring algorithms use O(log n) colors, with high probability. We also present the first efficient deterministic algorithm for the CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using O(log 12 n) colors.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Chen, Ke

Contributors dc:contributor

• Har-Peled, Sariel

• Computer Science

Language dc:language

eng

Identifier

(MiAaPQ)AAI3301113

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/81800