Modem illumination of monotone polygons

DOI10.1016/J.COMGEO.2017.05.010MaRDI QIDQ1699284zbMATH OpenOpenAlexFDO

Authors Oswin Aichholzer, R. Fabila-Monroy, D. Flores-Peñaloza, T. Hackl, J. Urrutia, Birgit Vogtenhuber

Publication date 19 February 2018

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.05062, http://hdl.handle.net/2117/6393

zbMATH Keywords

art gallery problem\(k\)-modem\(k\)-transmittermodem illuminationpolygon illumination

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Convex sets in (2) dimensions (including convex curves) (52A10)

Abstract: We study a generalization of the classical problem of the illumination of polygons. Instead of modeling a light source we model a wireless device whose radio signal can penetrate a given number $k$ of walls. We call these objects $k$-modems and study the minimum number of $k$-modems sufficient and sometimes necessary to illuminate monotone and monotone orthogonal polygons. We show that every monotone polygon with $n$ vertices can be illuminated with $$ $k$-modems. In addition, we exhibit examples of monotone polygons requiring at least $lceilfracn-22k+3ceil$ $k$-modems to be illuminated. For monotone orthogonal polygons with $n$ vertices we show that for $k=1$ and for even $k$, every such polygon can be illuminated with $$ $k$-modems, while for odd $kgeq3$, $$ $k$-modems are always sufficient. Further, by presenting according examples of monotone orthogonal polygons, we show that both bounds are tight.

Recommendations

• An upper bound on the \(k\)-modem illumination problem
• Illumination of Orthogonal Polygons with Orthogonal Floodlights
• Illumination with orthogonal floodlights
• Coverage with \(k\)-transmitters in the presence of obstacles
• Coverage with \(k\)-transmitters in the presence of obstacles

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• A combinatorial theorem in plane geometry
• An upper bound on the \(k\)-modem illumination problem
• Analysing local algorithms in location-aware quasi-unit-disk graphs
• Coverage with \(k\)-transmitters in the presence of obstacles
• Guard placement for efficient point-in-polygon proofs
• Improved Bounds for Wireless Localization
• Intersecting convex sets by rays
• Local solutions for global problems in wireless networks

Cited in

(8)

• Guarding orthogonal art galleries with sliding k-transmitters: hardness and approximation
• Conflict-free chromatic art gallery coverage
• Computing the \(k\)-visibility region of a point in a polygon
• Approximation algorithms for a geometric set cover problem
• On k-convex polygons
• \(k\)-Transmitter watchman routes
• Coverage with \(k\)-transmitters in the presence of obstacles
• Time-space trade-off for finding the \(k\)-visibility region of a point in a polygon

This page was built for publication: Modem illumination of monotone polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1699284)