A Facility Coloring Problem in 1-D

摘要: Consider a line segment R consisting of n facilities. Each facility is point on and it needs to be assigned exactly one the colors from given palette c colors. At an instant time only facilities particular color are ‘active’ all other ‘dormant’. For set color, we compute dimensional Voronoi diagram, find cell, i.e, maximum length. The users assumed uniformly distributed over they travel nearest among that active. Our objective assign in such way length longest cell minimized. We solve this optimization problem for various values c. propose optimal coloring scheme number being multiple as well general case where not When c, Θ(n) time. case, returns O(n 2logn)