4 papers
Decomposing a Simple Polygon with Geodesic Unit-Balls
Reilly Browne, Prahlad Narasimhan Kasthurirangan
We consider covering and partitioning a simple polygon into pieces which either have unit geodesic radius or unit geodesic diameter, using the -metric for distances. There…
Covering and Partitioning Complex Objects with Small Pieces
Anders Aamand, Mikkel Abrahamsen, Reilly Browne +6
We study the problems of covering or partitioning a polygon (possibly with holes) using a minimum number of small pieces, where a small piece is a connected sub-polygon contain…
Provable Methods for Searching with an Imperfect Sensor
Nilanjan Chakraborty, Prahlad Narasimhan Kasthurirangan, Joseph S. B. Mitchell +2
Assume that a target is known to be present at an unknown point among a finite set of locations in the plane. We search for it using a mobile robot that has imperfect sensing capab…
Dominator Coloring and CD Coloring in Almost Cluster Graphs
Aritra Banik, Prahlad Narasimhan Kasthurirangan, Venkatesh Raman
In this paper, we study two popular variants of Graph Coloring -- Dominator Coloring and CD Coloring. In both problems, we are given a graph and a natural number as inpu…