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

\(k\)-modem\(k\)-transmitterart gallery problemmodem illuminationpolygon illumination

Mathematics Subject Classification ID

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

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.

Review text

The modem illumination problem is a generalization of the art gallery problem. In the latter, a polygonal art gallery has to place a minimum number of guards at well chosen positions in the polygon in such a way that they cover every point of the polygon. In the modem illumination problem, the guards are wireless modems that should be able to reach every point in the polygon given that they are strong enough to transmit a signal though \(k\)-walls. The art gallery problem corresponds to \(k=0\). Properties are proved such as: Every \((k+2)\)-gon \(P\) can be illuminated by a \(k\)-modem placed anywhere in \(P\). But better bounds for the number of \(k\)-modems needed are derived for \(n\)-gons under extra conditions. A polygon \(P\) is monotone if there is a direction \(d\) such that every line parallel to \(d\) divides \(P\) in at most 2 parts and it is called orthogonal if adjacent edges are orthogonal. It is proved that to illuminate a monotone \(n\)-gon at most \(\lceil \frac{n-2}{2k-3}\rceil\) \(k\)-modems are sufficient and sometimes necessary. If moreover \(P\) is orthogonal then \(m\) \(k\)-modems are sufficient and sometimes necessary where \(m=\lceil \frac{n-2}{2k+4}\rceil\) if \(k=1\) or even and \(m=\lceil \frac{n-2}{2k+6}\rceil\) for \(k\geq3\) and odd.

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

• 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
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• 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
• Coverage with k-transmitters in the presence of obstacles
• Computing the \(k\)-visibility region of a point in a polygon
• Conflict-free chromatic art gallery coverage
• Time-space trade-off for finding 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

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)