|
|
Research
Geometric set cover on a set of line segments
I am currently engrossed in investigating a geometric set covering problem called Line Segment Cover. The problem has close connection to Line Cover, and Set Cover with Intersection 1. Very less is known about the hardness of approximating Line Segment Cover. It is part of a class of problems called Art Gallery Problems. For Example, imagine a road network of a city. The network can be abstracted as a set of line segments, and a set of points covering these segments would correspond to a set of locations on the network which together can observe the entire network.
|