Orthogonal terrain guarding is NP-complete

Conference paper

Bonnet, E. and Giannopoulos, P. 2018. Orthogonal terrain guarding is NP-complete. 34th International Symposium on Computational Geometry (SoCG 2018). Budapest, Hungary 11 - 14 Jun 2018 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany. pp. 11:1-11:15 https://doi.org/10.4230/LIPIcs.SoCG.2018.11
TypeConference paper
TitleOrthogonal terrain guarding is NP-complete
AuthorsBonnet, E. and Giannopoulos, P.
Research GroupFoundations of Computing group
Conference34th International Symposium on Computational Geometry (SoCG 2018)
Page range11:1-11:15
ISSN1868-8969
ISBN
Hardcover9783959770668
PublisherLeibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
Publication dates
Print05 May 2018
Publication process dates
Deposited26 Feb 2018
Accepted14 Feb 2018
Output statusPublished
Accepted author manuscript
License
Additional information

Article number = 11

Digital Object Identifier (DOI)https://doi.org/10.4230/LIPIcs.SoCG.2018.11
LanguageEnglish
Book title34th International Symposium on Computational Geometry (SoCG 2018)
Permalink -

https://repository.mdx.ac.uk/item/877q4

Log in to edit

Download files

Accepted author manuscript
p11-bonnet.pdf
License: CC BY 4.0

  • 43
    total views
  • 12
    total downloads
  • 3
    views this month
  • 1
    downloads this month

Export as

Related outputs

Low-crossing spanning trees: an alternative proof and experiments
Giannopoulos, P., Konzack, M. and Mulzer, W. 2014. Low-crossing spanning trees: an alternative proof and experiments. European Workshop on Computational Geometry. Ein-Gedi, Israel 03 - 05 Mar 2014
QPTAS and subexponential algorithm for maximum clique on disk graphs
Bonnet, E., Giannopoulos, P., Kim, E., Rzążewski, P. and Sikora, F. 2018. QPTAS and subexponential algorithm for maximum clique on disk graphs. 34th International Symposium on Computational Geometry. Budapest, Hungary 11 - 14 Jun 2018 Dagstuhl, Germany Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany. pp. 12:1-12:15 https://doi.org/10.4230/LIPIcs.SoCG.2018.12
On the parameterized complexity of red-blue points separation
Bonnet, E., Giannopoulos, P. and Lampis, M. 2018. On the parameterized complexity of red-blue points separation. 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Vienna, Austria 06 - 08 Sep 2017 LIPICS Schloss Dagstuhl. pp. 8:1-8:13 https://doi.org/10.4230/LIPIcs.IPEC.2017.8
Minimum cell connection in line segment arrangements
Alt, H., Cabello, S., Giannopoulos, P. and Knauer, C. 2017. Minimum cell connection in line segment arrangements. International Journal of Computational Geometry and Applications. 27 (3), pp. 159-176. https://doi.org/10.1142/s0218195917500017
The complexity of separating points in the plane
Cabello, S. and Giannopoulos, P. 2016. The complexity of separating points in the plane. Algorithmica. 74 (2), pp. 643-663. https://doi.org/10.1007/s00453-014-9965-6