Geometric Systems of Unbiased Representatives

Let $P$ be a set of points in $mathbb{R}^d$, $B$ a bicoloring of $P$ and $Oo$ a family of geometric objects (that is, intervals, boxes, balls, etc). An object from $Oo$ is called balanced with respect to $B$ if it contains the same number of points from each color of $B$. For a collection $B$ of bicolorings of $P$, a geometric system of unbiased representatives (G-SUR) is a subset $OosubseteqOo$ such that for any bicoloring $B$ of $B$ there is an object in $Oo$ that is balanced with respect to $B$. We study the problem of finding G-SURs. We obtain general bounds on the size of G-SURs consisting of intervals, size-restricted intervals, axis-parallel boxes and Euclidean balls. We show that the G-SUR problem is NP-hard even in the simple case of points on a line and interval ranges. Furthermore, we study a related problem on determining the size of the largest and smallest balanced intervals for points on the real line with a random distribution and coloring. Our results are a natural extension to a geometric context of the work initiated by Balachandran et al. on arbitrary systems of unbiased representatives.

Fixed-parameter tractable algorithms for Tracking Shortest Paths

We consider the parameterized complexity of the problem of tracking shortest s-t paths in graphs, motivated by applications in security and wireless networks. Given an undirected and unweighted graph with a source s and a destination t, Tracking Shortest Paths asks if there exists a k-sized subset of vertices (referred to as tracking set) that intersects each shortest s-t path in a distinct set of vertices. We first generalize this problem for set systems, namely Tracking Set System, where given a family of subsets of a universe, we are required to find a subset of elements from the universe that has a unique intersection with each set in the family. Tracking Set System is shown to be fixed-parameter tractable due to its relation with a known problem, Test Cover. By a reduction to the well-studied d-hitting set problem, we give a polynomial (with respect to k) kernel for the case when the set sizes are bounded by d. This also helps solving Tracking Shortest Paths when the input graph diameter is bounded by d. While the results for Tracking Set System help to show that Tracking Shortest Paths is fixed-parameter tractable, we also give an independent algorithm by using some preprocessing rules, resulting in an improved running time.

Geometric Planar Networks on Bichromatic Points

We study four classical graph problems -- Hamiltonian path, Traveling salesman, Minimum spanning tree, and Minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. These problems have been widely studied for points in the Euclidean plane, and many of them are NP-hard. In this work, we consider these problems in two restricted settings: (i) collinear points and (ii) equidistant points on a circle. We show that almost all of these problems can be solved in linear time in these constrained, yet non-trivial settings.

Network Optimization on Partitioned Pairs of Points

Given $n$ pairs of points, $mathcal{S} = {{p_1, q_1}, {p_2, q_2}, dots, {p_n, q_n}}$, in some metric space, we study the problem of two-coloring the points within each pair, red and blue, to optimize the cost of a pair of node-disjoint networks, one over the red points and one over the blue points. In this paper we consider our network structures to be spanning trees, traveling salesman tours or matchings. We consider several different weight functions computed over the network structures induced, as well as several different objective functions. We show that some of these problems are NP-hard, and provide constant factor approximation algorithms in all cases.

Polynomial Time Algorithms for Bichromatic Problems

In this article, we consider a collection of geometric problems involving points colored by two colors (red and blue), referred to as bichromatic problems. The motivation behind studying these problems is two fold; (i) these problems appear naturally and frequently in the fields like Machine learning, Data mining, and so on, and (ii) we are interested in extending the algorithms and techniques for single point set (monochromatic) problems to bichromatic case. For all the problems considered in this paper, we design low polynomial time exact algorithms. These algorithms are based on novel techniques which might be of independent interest.

The $p$-Center Problem in Tree Networks Revisited

We present two improved algorithms for weighted discrete $p$-center problem for tree networks with $n$ vertices. One of our proposed algorithms runs in $O(n log n + p log^2 n log(n/p))$ time. For all values of $p$, our algorithm thus runs as fast as or faster than the most efficient $O(nlog^2 n)$ time algorithm obtained by applying Coles speed-up technique [cole1987] to the algorithm due to Megiddo and Tamir [megiddo1983], which has remained unchallenged for nearly 30 years. Our other algorithm, which is more practical, runs in $O(n log n + p^2 log^2(n/p))$ time, and when $p=O(sqrt{n})$ it is faster than Megiddo and Tamirs $O(n log^2n loglog n)$ time algorithm [megiddo1983].

Discrete Voronoi Games and $epsilon$-Nets, in Two and Three Dimensions

The one-round discrete Voronoi game, with respect to a $n$-point user set $U$, consists of two players Player 1 ($mathcal{P}_1$) and Player 2 ($mathcal{P}_2$). At first, $mathcal{P}_1$ chooses a set of facilities $F_1$ following which $mathcal{P}_2$ chooses another set of facilities $F_2$, disjoint from $F_1$. The payoff of $mathcal{P}_2$ is defined as the cardinality of the set of points in $U$ which are closer to a facility in $F_2$ than to every facility in $F_1$, and the payoff of $mathcal{P}_1$ is the difference between the number of users in $U$ and the payoff of $mathcal{P}_2$. The objective of both the players in the game is to maximize their respective payoffs. In this paper we study the one-round discrete Voronoi game where $mathcal{P}_1$ places $k$ facilities and $mathcal{P}_2$ places one facility and we have denoted this game as $VG(k,1)$. Although the optimal solution of this game can be found in polynomial time, the polynomial has a very high degree. In this paper, we focus on achieving approximate solutions to $VG(k,1)$ with significantly better running times. We provide a constant-factor approximate solution to the optimal strategy of $mathcal{P}_1$ in $VG(k,1)$ by establishing a connection between $VG(k,1)$ and weak $epsilon$-nets. To the best of our knowledge, this is the first time that Voronoi games are studied from the point of view of $epsilon$-nets.

Voronoi Game on Graphs

textit{Voronoi game} is a geometric model of competitive facility location problem played between two players. Users are generally modeled as points uniformly distributed on a given underlying space. Each player chooses a set of points in the underlying space to place their facilities. Each user avails service from its nearest facility. Service zone of a facility consists of the set of users which are closer to it than any other facility. Payoff of each player is defined by the quantity of users served by all of its facilities. The objective of each player is to maximize their respective payoff. In this paper we consider the two players {it Voronoi game} where the underlying space is a road network modeled by a graph. In this framework we consider the problem of finding $k$ optimal facility locations of Player 2 given any placement of $m$ facilities by Player 1. Our main result is a dynamic programming based polynomial time algorithm for this problem on tree network. On the other hand, we show that the problem is strongly $mathcal{NP}$-complete for graphs. This proves that finding a winning strategy of P2 is $mathcal{NP}$-complete. Consequently, we design an $1-frac{1}{e}$ factor approximation algorithm, where $e approx 2.718$.

On Packing Almost Half of a Square with Anchored Rectangles: A Constructive Approach

In this paper, we consider the following geometric puzzle whose origin was traced to Allan Freedman cite{croft91,tutte69} in the 1960s by Dumitrescu and T{o}th cite{adriancasaba2011}. The puzzle has been popularized of late by Peter Winkler cite{Winkler2007}. Let $P_{n}$ be a set of $n$ points, including the origin, in the unit square $U = [0,1]^2$. The problem is to construct $n$ axis-parallel and mutually disjoint rectangles inside $U$ such that the bottom-left corner of each rectangle coincides with a point in $P_{n}$ and the total area covered by the rectangles is maximized. We would term the above rectangles as emph{anchored rectangles}. The longstanding conjecture has been that at least half of $U$ can be covered when anchored rectangles are properly placed. Dumitrescu and T{o}th cite{Dumitrescu2012} have shown a construction method that can cover at least $0.09121$, i.e., roughly $9%$ of the area.

An Existential Proof of the Conjecture on Packing Anchored Rectangles

Let $P_{n}$ be a set of $n$ points, including the origin, in the unit square $U = [0,1]^2$. We consider the problem of constructing $n$ axis-parallel and mutually disjoint rectangles inside $U$ such that the bottom-left corner of each rectangle coincides with a point in $P_{n}$ and the total area covered by the rectangles is maximized cite{ibmpuzzle}, cite{Winkler2007}, cite{Winkler2010a}, cite{Winkler2010b}. The longstanding conjecture has been that at least half of $U$ can be covered when such rectangles are properly placed. In this paper, we give an existential proof of the conjecture.