Publications

Results 3376–3400 of 9,998

Search results

Jump to search filters

Geometric Hitting Set for Segments of Few Orientations

Theory of Computing Systems

Fekete, Sandor P.; Huang, Kan; Mitchell, Joseph S.B.; Parekh, Ojas D.; Phillips, Cynthia A.

We study several natural instances of the geometric hitting set problem for input consisting of sets of line segments (and rays, lines) having a small number of distinct slopes. These problems model path monitoring (e.g., on road networks) using the fewest sensors (the “hitting points”). We give approximation algorithms for cases including (i) lines of 3 slopes in the plane, (ii) vertical lines and horizontal segments, (iii) pairs of horizontal/vertical segments. We give hardness and hardness of approximation results for these problems. We prove that the hitting set problem for vertical lines and horizontal rays is polynomially solvable.

More Details
TYPE Journal Article YEAR 2018
DOIOSTIScopus
Results 3376–3400 of 9,998
Results 3376–3400 of 9,998