Variants of Visibility and their Complexity

&
Mathematical Logic Quarterly 44 (4):522-528 (1998)
  Copy   BIBTEX

Abstract

First we give an overview about variants of visibility and related problems. Then we prove that some guarding and covering problems are NP-hard for ortho-polygons with holes, using a so-called vertex cover technique

Categories

Add categories

Keywords

Reprint years

DOI

10.1002/malq.19980440411

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,592

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons.Dietmar Schuchardt & Hans-Dietrich Hecker - 1995 - Mathematical Logic Quarterly 41 (2):261-267.
Complexity and sustainability.Jennifer Wells - 2013 - New York: Routledge.
On visibility and power: An Arendtian corrective of Foucault. [REVIEW]Neve Gordon - 2002 - Human Studies 25 (2):125-145.
To appraise developmental difficulty or mental demand, relational complexity is not enough.Juan Pascual-Leone - 1998 - Behavioral and Brain Sciences 21 (6):843-844.
Visual Culture and the Fight for Visibility.Markus Schroer - 2014 - Journal for the Theory of Social Behaviour 44 (2):206-228.
Are complex systems hard to evolve?Andy Adamatzky & Larry Bull - 2009 - Complexity 14 (6):15-20.
Complexity of networks II: The set complexity of edge‐colored graphs.Tomasz M. Ignac, Nikita A. Sakhanenko & David J. Galas - 2012 - Complexity 17 (5):23-36.
Concept identification as a function of task complexity and distribution of practice.Frederick G. Brown & E. James Archer - 1956 - Journal of Experimental Psychology 52 (5):316.
Basic logic: Reflection, symmetry, visibility.Giovanni Sambin, Giulia Battilotti & Claudia Faggian - 2000 - Journal of Symbolic Logic 65 (3):979-1013.
Infinite Versions of Some Problems from Finite Complexity Theory.Jeffry L. Hirst & Steffen Lempp - 1996 - Notre Dame Journal of Formal Logic 37 (4):545-553.
On the complexity of the pancake problem.Fuxiang Yu - 2007 - Mathematical Logic Quarterly 53 (4):532-546.
A P‐Completeness Result for Visibility Graphs of Simple Polygons.Jana Dietel & Hans-Dietrich Hecker - 2000 - Mathematical Logic Quarterly 46 (3):361-375.
Synthetic analysis: How science combats complexity.Sunny Auyang - manuscript

Analytics

Added to PP
2014-01-16

Downloads
16 (#900,320)

6 months
2 (#1,192,610)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references