Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 2/2018

06.02.2017

Geometric Hitting Set for Segments of Few Orientations

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

Erschienen in: Theory of Computing Systems | Ausgabe 2/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.
Vorheriger Artikel Constant-Time Local Computation Algorithms
Nächster Artikel Scheduling Parallel Jobs Online with Convex and Concave Parallelizability

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
Afshani, P., Berglin, E., van Duijn, I., Nielsen, J.S.: Applications of incidence bounds in point covering problems. In: Proceedings 32nd International Symposium on Computational Geometry, LIPIcs, 51, 60:1–60:15, Schloss Dagstuhl - Leibniz-Zentrum Fuer Informatik (2016)
2.
3.
Aronov, B., Ezra, E., Sharir, M.: Small-size ε-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248–3282 (2010)MathSciNetCrossRefMATH
4.
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer Science & Business Media (2012)
5.
Balaban, I.J.: An optimal algorithm for finding segment intersections. In: Proceedings of 11th Symposium on Computational Geometry 211–219, ACM (1995)
6.
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)CrossRefMATH
7.
Brimkov, V.E.: Approximability issues of guarding a set of segments. Int. J. Comput. Math. 90(8), 1653–1667 (2013)CrossRefMATH
8.
Brimkov, V.E., Leach, A., Mastroianni, M., Wu, J.: Experimental study on approximation algorithms for guarding sets of line segments. In: Advances in Visual Computing, 592–601, Springer (2010)
9.
Brimkov, V.E., Leach, A., Mastroianni, M., Wu, J.: Guarding a set of line segments in the plane. Theor. Comput. Sci. 412(15), 1313–1324 (2011)MathSciNetCrossRefMATH
10.
Brimkov, V.E., Leach, A., Wu, J., Mastroianni, M.: Approximation algorithms for a geometric set cover problem. Discrete Applied Math 160, 1039–1052 (2012)MathSciNetCrossRefMATH
11.
Brodėn, B., Hammar, M., Nilsson, B.J.: Guarding Lines and 2-Link Polygons is APX-Hard. In: Proceedings of 13th Canadian Conference on Computational Geometry, 45–48 (2001)
12.
Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14, 263–279 (1995)MathSciNetCrossRefMATH
13.
Carr, R.D., Fujito, T., Konjevod, G., Parekh, O.: A 2 1/10-approximation algorithm for a generalization of the weighted edge-dominating set problem. In: European Symposium on Algorithms, 132–142, Springer (2000)
14.
15.
Clarkson, K.L.: Algorithms for polytope covering and approximation. In: Algorithms and Data Structures, 246–252, Springer (1993)
16.
Clarkson, K.L., Varadarajan, K.: Improved approximation algorithms for geometric set cover. Discrete Comput. Geom. 37(1), 43–58 (2007)MathSciNetCrossRefMATH
17.
Dinur, I., Steurer, D.: Analytical Approach to Parallel Repetition. In: Proceedings of 46th Symposium on Theory of Computing, 624–633, ACM (2014)
18.
Dom, M., Fellows, M.R., Rosamond, F.A.: Parameterized complexity of stabbing rectangles and squares in the plane. In: WALCOM: Algorithms and Computation, 298–309, Springer (2009)
19.
Duh, R.C., Fürer, M.: Approximation of k-set cover by semi-local optimization. In: Proceedings of 29th Symposium on Theory of Computing, 256–264, ACM (1997)
20.
Dumitrescu, A., Jiang, M.: On the approximability of covering points by lines and related problems. Computational Geometry: Theory and Applications 48 (9), 703–717 (2015)MathSciNetCrossRefMATH
21.
Even, G., Levi, R., Rawitz, D., Schieber, B., Shahar, S.M., Sviridenko, M.: Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs. ACM Transactions on Algorithms 4(3), 34:1–34:17 (2008)MathSciNetCrossRef
22.
23.
Gaur, D.R., Bhattacharya, B.: Covering points by axis parallel lines. In: Proceedings 23rd European Workshop on Computational Geometry, 42–45 (2007)
24.
Gaur, D.R., Ibaraki, T., Krishnamurti, R.: Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem. In: Proceedings of European Symposium on Algorithms, 211–219, Springer (2000)
25.
Giannopoulos, P., Knauer, C., Rote, G., Werner, D.: Fixed-parameter tractability and lower bounds for stabbing problems. Computational Geometry: Theory and Applications 46, 839–860 (2013)MathSciNetCrossRefMATH
26.
Hassin, R., Megiddo, N.: Approximation algorithms for hitting objects with straight lines. Discret. Appl. Math. 30(1), 29–42 (1991)MathSciNetCrossRefMATH
27.
Heednacram, A.: The NP-Hardness of Covering Points with Lines, Paths and Tours and their Tractability with FPT-Algorithms, Ph.D. thesis, Griffith University (2010)
28.
Hochbaum, D.S., Maas, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32, 130–136 (1985)MathSciNetCrossRefMATH
29.
Joshi, A., Narayanaswamy, N.: Approximation algorithms for hitting triangle-free sets of line segments. In: Proceedings of 14th Scandinavian Symposium and Workshops on Algorithm Theory, 357–367, Springer (2014)
30.
Kovaleva, S., Spieksma, F.C.: Approximation algorithms for rectangle stabbing and interval stabbing problems. SIAM J. Discret. Math. 20(3), 748–768 (2006)MathSciNetCrossRefMATH
31.
Kratsch, S., Philip, G., Ray, S.: Point line cover: the easy kernel is essentially tight. In: Proceedings of 25th ACM-SIAM Symposium on Discrete Algorithms, 1596–1606 (2014)
32.
Kumar, V.A., Arya, S., Ramesh, H.: Hardness of set cover with intersection 1. In: Proceedings of 27th International Colloquium on Automata, Languages and Programming, 624–635 (2000)
33.
34.
Megiddo, N., Tamir, A.: On the complexity of locating linear facilities in the plane. Oper. Res. Lett. 1(5), 194–197 (1982)MathSciNetCrossRefMATH
35.
36.
O’Rourke, J.: Art gallery theorems and algorithms. The international series of monographs on computer science. Oxford University Press, New York (1987)
37.
38.
Metadaten
Titel
Geometric Hitting Set for Segments of Few Orientations
verfasst von
Sándor P. Fekete
Kan Huang
Joseph S. B. Mitchell
Ojas Parekh
Cynthia A. Phillips
Publikationsdatum
06.02.2017
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 2/2018
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-016-9744-7

Weitere Artikel der Ausgabe 2/2018

Theory of Computing Systems 2/2018 Zur Ausgabe

OriginalPaper

On the Smoothness of Paging Algorithms

OriginalPaper

Scheduling Parallel Jobs Online with Convex and Concave Parallelizability

EditorialNotes

WAOA 2015 Special Issue on TOCS

OriginalPaper

Maximum ATSP with Weights Zero and One via Half-Edges

OriginalPaper

Approximation Algorithms for Connected Graph Factors of Minimum Weight

OriginalPaper

Constant-Time Local Computation Algorithms

Premium Partner

    Bildnachweise