SCIENCE@home

Altitude Terrain Guarding and Guarding Uni-Monotone Polygons

Stephan Friedrichs,V. Polishchuk,Christiane Schmidt

Published 2018 in Computational geometry

ABSTRACT

We show that the problem of guarding an $x$-monotone terrain from an altitude line and the problem of guarding a uni-monotone polygon are equivalent. We present a polynomial time algorithm for both problems, and show that the cardinality of a minimum guard set and the cardinality of a maximum witness set coincide. Thus, uni-monotone polygons are perfect; this result also extends to monotone mountains.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-22 of 22 references · Page 1 of 1

CITED BY