Geometric hitting set for segments of few orientations

Sándor P. Fekete; Kan Huang; Joseph S.B. Mitchell; Ojas Parekh; Cynthia A. Phillips

doi:10.1007/978-3-319-28684-6_13

Geometric hitting set for segments of few orientations

Sándor P. Fekete
, Kan Huang
, Joseph S.B. Mitchell
, Ojas Parekh
, Cynthia A. Phillips

Applied Mathematics and Statistics

Technical University of Braunschweig
Stony Brook University
Sandia National Laboratories, New Mexico

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers
Editors	Laura Sanità, Martin Skutella
Publisher	Springer Verlag
Pages	145-157
Number of pages	13
ISBN (Print)	9783319286839
DOIs	https://doi.org/10.1007/978-3-319-28684-6_13
State	Published - 2015
Event	13th International Workshop on Approximation and Online Algorithms, WAOA 2015 - Patras, Greece Duration: Sep 17 2015 → Sep 18 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9499
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th International Workshop on Approximation and Online Algorithms, WAOA 2015
Country/Territory	Greece
City	Patras
Period	09/17/15 → 09/18/15

Access to Document

10.1007/978-3-319-28684-6_13

Cite this

Fekete, S. P., Huang, K., Mitchell, J. S. B., Parekh, O., & Phillips, C. A. (2015). Geometric hitting set for segments of few orientations. In L. Sanità, & M. Skutella (Eds.), Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers (pp. 145-157). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9499). Springer Verlag. https://doi.org/10.1007/978-3-319-28684-6_13

Fekete, Sándor P. ; Huang, Kan ; Mitchell, Joseph S.B. et al. / Geometric hitting set for segments of few orientations. Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers. editor / Laura Sanità ; Martin Skutella. Springer Verlag, 2015. pp. 145-157 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5cbabfbe55314265b33a25c8dc071e41,

title = "Geometric hitting set for segments of few orientations",

abstract = "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.",

author = "Fekete, \{S{\'a}ndor P.\} and Kan Huang and Mitchell, \{Joseph S.B.\} and Ojas Parekh and Phillips, \{Cynthia A.\}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 13th International Workshop on Approximation and Online Algorithms, WAOA 2015 ; Conference date: 17-09-2015 Through 18-09-2015",

year = "2015",

doi = "10.1007/978-3-319-28684-6\_13",

language = "English",

isbn = "9783319286839",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "145--157",

editor = "Laura Sanit{\`a} and Martin Skutella",

booktitle = "Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers",

}

Fekete, SP, Huang, K, Mitchell, JSB, Parekh, O & Phillips, CA 2015, Geometric hitting set for segments of few orientations. in L Sanità & M Skutella (eds), Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9499, Springer Verlag, pp. 145-157, 13th International Workshop on Approximation and Online Algorithms, WAOA 2015, Patras, Greece, 09/17/15. https://doi.org/10.1007/978-3-319-28684-6_13

Geometric hitting set for segments of few orientations. / Fekete, Sándor P.; Huang, Kan; Mitchell, Joseph S.B. et al.
Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers. ed. / Laura Sanità; Martin Skutella. Springer Verlag, 2015. p. 145-157 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9499).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Geometric hitting set for segments of few orientations

AU - Fekete, Sándor P.

AU - Huang, Kan

AU - Mitchell, Joseph S.B.

AU - Parekh, Ojas

AU - Phillips, Cynthia A.

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84956708672

U2 - 10.1007/978-3-319-28684-6_13

DO - 10.1007/978-3-319-28684-6_13

M3 - Conference contribution

AN - SCOPUS:84956708672

SN - 9783319286839

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 145

EP - 157

BT - Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers

A2 - Sanità, Laura

A2 - Skutella, Martin

PB - Springer Verlag

T2 - 13th International Workshop on Approximation and Online Algorithms, WAOA 2015

Y2 - 17 September 2015 through 18 September 2015

ER -

Fekete SP, Huang K, Mitchell JSB, Parekh O, Phillips CA. Geometric hitting set for segments of few orientations. In Sanità L, Skutella M, editors, Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers. Springer Verlag. 2015. p. 145-157. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-28684-6_13

Geometric hitting set for segments of few orientations

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this