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.
First we explore ray sensor networks in the plane, whose resilience 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 barrier graph of the network. We show that barrier graphs are perfect (Berge) graphs and have a rigid neighborhood structure due to the rays' geometry.
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 k locations with n (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 k = 2 in both cases. We provide asymptotically tight answers for question (1) when k = 3, 4 and the locations are in convex position. We also provide asymptotic lower bounds for question (1) for any k.
Finally, we generalize these extremal problems to d dimensions. For the d-dimensional version of question (1) we provide asymptotic lower and upper bounds for any combination of k and d, though these bounds do not meet.
","abstract_html":"<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>","abstract_has_math":false,"creators":["Boyer, Kirk Anthony"],"institution":null,"degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Paul Horn, Ph.D.","Mario A. Lopez, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019-01-01T08:00:00Z","date_published":"2019-01-01T08:00:00Z","updated_at":"2026-07-24T02:03:26Z","subjects":["Computational geometry","Extremal problems","Sensor networks","Geometry and Topology","Mathematics"],"languages":["en"],"rights":["Copyright is held by the author. User is responsible for all copyright compliance.
"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.du.edu/etd/1555","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Paul Horn, Ph.D.","Mario A. Lopez, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Boyer, Kirk Anthony"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2019-07-11T07:00:00Z"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computational geometry","Extremal problems","Sensor networks","Geometry and Topology","Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright is held by the author. User is responsible for all copyright compliance.
"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.du.edu/etd/1555"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
First we explore ray sensor networks in the plane, whose resilience 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 barrier graph of the network. We show that barrier graphs are perfect (Berge) graphs and have a rigid neighborhood structure due to the rays' geometry.
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 k locations with n (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 k = 2 in both cases. We provide asymptotically tight answers for question (1) when k = 3, 4 and the locations are in convex position. We also provide asymptotic lower bounds for question (1) for any k.
Finally, we generalize these extremal problems to d dimensions. For the d-dimensional version of question (1) we provide asymptotic lower and upper bounds for any combination of k and d, though these bounds do not meet.
"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Barrier Graphs and Extremal Questions on Line, Ray, Segment, and Hyperplane Sensor Networks"]}]}],"canonical_facts":{"dc:contributor":["Paul Horn, Ph.D.","Mario A. Lopez, Ph.D."],"dc:creator":["Boyer, Kirk Anthony"],"dc:date.available":["2019-07-11T07:00:00Z"],"dc:description.abstract":["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.
First we explore ray sensor networks in the plane, whose resilience 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 barrier graph of the network. We show that barrier graphs are perfect (Berge) graphs and have a rigid neighborhood structure due to the rays' geometry.
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 k locations with n (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 k = 2 in both cases. We provide asymptotically tight answers for question (1) when k = 3, 4 and the locations are in convex position. We also provide asymptotic lower bounds for question (1) for any k.
Finally, we generalize these extremal problems to d dimensions. For the d-dimensional version of question (1) we provide asymptotic lower and upper bounds for any combination of k and d, though these bounds do not meet.
"],"dc:format":["application/pdf"],"dc:identifier":["https://digitalcommons.du.edu/etd/1555"],"dc:language":["en"],"dc:rights":["Copyright is held by the author. User is responsible for all copyright compliance.
"],"dc:subject":["Computational geometry","Extremal problems","Sensor networks","Geometry and Topology","Mathematics"],"dc:title":["Barrier Graphs and Extremal Questions on Line, Ray, Segment, and Hyperplane Sensor Networks"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."]},"updated_at":"2026-07-24T02:03:26Z"}