Search Constraints

Start Over
Filtering by: Creator Das, Sandip Remove constraint Creator: Das, Sandip

Search Results

  • A facility coloring problem in 1-D

    Resource Type:
    Conference Proceeding
    Creator:
    Maheshwari, Anil, Nandy, Ayan, Smid, Michiel, and Das, Sandip
    Abstract:
    Consider a line segment R consisting of n facilities. Each facility is a point on R and it needs to be assigned exactly one of the colors from a given palette of c colors. At an instant of time only the facilities of one particular color are 'active' and all other facilities are 'dormant'. For the set of facilities of a particular color, we compute the one dimensional Voronoi diagram, and find the cell, i.e, a segment of maximum length. The users are assumed to be uniformly distributed over R and they travel to the nearest among the facilities of that particular color that is active. Our objective is to assign colors to the facilities in such a way that the length of the longest cell is minimized. We solve this optimization problem for various values of n and c. We propose an optimal coloring scheme for the number of facilities n being a multiple of c as well as for the general case where n is not a multiple of c. When n is a multiple of c, we compute an optimal scheme in Θ(n) time. For the general case, we propose a coloring scheme that returns the optimal in O(n2logn) time.
    Date Created:
    2014-01-01

  • The discrete voronoi game in a simple polygon

    Resource Type:
    Conference Proceeding
    Creator:
    Smid, Michiel, Maheshwari, Anil, Das, Sandip, and Banik, Aritra
    Abstract:
    Let P be a simple polygon with m vertices and let be a set of n points in P. We consider the points of to be users. We consider a game with two players and. In this game, places a point facility inside P, after which places another point facility inside P. We say that a user is served by its nearest facility, where distances are measured by the geodesic distance in P. The objective of each player is to maximize the number of users they serve. We show that for any given placement of a facility by, an optimal placement for can be computed in O(m + n(logn + logm)) time. We also provide a polynomial-time algorithm for computing an optimal placement for.
    Date Created:
    2013-10-08