Barrier Graphs and Extremal Questions on Line, Ray, Segment, and Hyperplane Sensor Networks

<p>A sensor network is typically modeled as a collection of spatially distributed objects with the same shape, generally for the purpose of surveilling or protecting areas and locations. In this dissertation we address several questions relating to sensors with linear shapes: line, line segment, and rays in the plane, and hyperplanes in higher dimensions.</p> <p>First we explore ray sensor networks in the plane, whose <em>resilience</em> is the number of sensors that must be crossed by an agent traveling between two known locations. The coverage of such a network is described by a particular tripartite graph, the <em>barrier graph</em> of the network. We show that barrier graphs are perfect (Berge) graphs and have a rigid neighborhood structure due to the rays' geometry.</p> <p>We introduce two extremal problems for networks in the plane made of line sensors, line segment sensors, or ray sensors, which informally ask how well it is possible to simultaneously protect <em>k</em> locations with<em> n</em> (line/ray/segment)-shaped sensors from intruders. The first question allows any number of intruders, while the second assumes there is a lone intruder. We show these are questions to be answered separately, and provide complete answers for <em>k</em> = 2 in both cases. We provide asymptotically tight answers for question (1) when <em>k</em> = 3, 4 and the locations are in convex position. We also provide asymptotic lower bounds for question (1) for any <em>k</em>.</p> <p>Finally, we generalize these extremal problems to <em>d</em> dimensions. For the <em>d</em>-dimensional version of question (1) we provide asymptotic lower and upper bounds for any combination of <em>k</em> and <em>d</em>, though these bounds do not meet.</p>

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Year dc:date.available

2019

Author dc:creator

• Boyer, Kirk Anthony

Contributors dc:contributor

• Paul Horn, Ph.D.
• Mario A. Lopez, Ph.D.

• Computational geometry
• Extremal problems
• Sensor networks
• Geometry and Topology
• Mathematics

Statement dc:rights

• <p>Copyright is held by the author. User is responsible for all copyright compliance.</p>

Language dc:language

en

Repository record dc:identifier

https://digitalcommons.du.edu/etd/1555

OAI identifier oai:identifier

oai:digitalcommons.du.edu:etd-2555