Opaque Forest Problem

In discrete geometry, an opaque set is a system of curves or other set in the plane that blocks all lines of sight across a polygon, circle, or other shape. Opaque sets have also been called barriers, beam detectors, opaque covers, or (in cases where they have the form of a forest of line segments or other curves) opaque forests. Opaque sets were introduced by Stefan Mazurkiewicz in 1916, and the problem of minimizing their total length was posed by Frederick Bagemihl in 1959.

For instance, visibility through a unit square can be blocked by its four boundary edges, with length 4, but a shorter opaque forest blocks visibility across the square with length $\sqrt2+\tfrac12\sqrt6\approx 2.639$. It is unproven whether this is the shortest possible opaque set for the square, and for most other shapes this problem similarly remains unsolved. The shortest opaque set for any bounded convex set in the plane has length at most the perimeter of the set, and at least half the perimeter. For the square, a slightly stronger lower bound than half the perimeter is known. Another convex set whose opaque sets are commonly studied is the unit circle, for which the shortest connected opaque set has length $2+\pi$. Without the assumption of connectivity, the shortest opaque set for the circle has length at least $\pi$ and at most $4.7998$.

Several published algorithms claiming to find the shortest opaque set for a convex polygon were later shown to be incorrect. Nevertheless, it is possible to find an opaque set with a guaranteed approximation ratio in linear time, or to compute the subset of the plane whose visibility is blocked by a given system of line segments in polynomial time.

Definitions

Every set $S$ in the plane blocks the visibility through a superset of $S$, its ''coverage'' $C$. $C$ consists of points for which all lines through the point intersect $S$. If a given set $K$ forms a subset of the coverage of $S$, then $S$ is said to be an ''opaque set'', ''barrier'', ''beam detector'', or ''opaque cover'' for $K$. If, additionally, $S$ has a special form, consisting of finitely many line segments whose union forms a forest, it is called an ''opaque forest''. There are many possible opaque sets for any given set $K$, including $K$ itself, and many possible opaque forests. For opaque forests, or more generally for systems of rectifiable curves, their length can be measured in the standard way. For more general point sets, one-dimensional Hausdorff measure can be used, and agrees with the standard length in the cases of line segments and rectifiable curves.

Most research on this problem assumes that the given set $K$ is a convex set. When it is not convex but merely a connected set, it can be replaced by its convex hull without changing its opaque sets. Some variants of the problem restrict the opaque set to lie entirely inside or entirely outside $K$. In this case, it is called an interior barrier or an exterior barrier, respectively. When this is not specified, the barrier is assumed to have no constraints on its location. Versions of the problem in which the opaque set must be connected or form a single curve have also been considered. It is not known whether every convex set $P$ has a shortest opaque set, or whether instead the lengths of its opaque sets might approach an infimum without ever reaching it. Every opaque set for $P$ can be approximated arbitrarily closely in length by an opaque forest, and it has been conjectured that every convex polygon has an opaque forest as its shortest opaque set, but this has not been proven.

Bounds

When the region to be covered is a convex set, the length of its shortest opaque set must be at least half its perimeter and at most its perimeter. For some regions, additional improvements to these bounds can be made.

Upper bound

If $K$ is a bounded convex set to be covered, then its boundary $\partial K$ forms an opaque set whose length is the perimeter $, \partial K,$. Therefore, the shortest possible length of an opaque set is at most the perimeter. For sets $K$ that are strictly convex, meaning that there are no line segments on the boundary, and for interior barriers, this bound is tight. Every point on the boundary must be contained in the opaque set, because every boundary point has a tangent line through it that cannot be blocked by any other points. The same reasoning shows that for interior barriers of convex polygons, all vertices must be included. Therefore, the minimum Steiner tree of the vertices is the shortest ''connected'' opaque set, and the traveling salesperson path of the vertices is the shortest ''single-curve'' opaque set. However, for interior barriers of non-polygonal convex sets that are not strictly convex, or for barriers that are not required to be connected, other opaque sets may be shorter; for instance, it is always possible to omit the longest line segment of the boundary. In these cases, the perimeter or Steiner tree length provide an upper bound on the length of an opaque set.

Lower bound

There are several proofs that an opaque set for any convex set $K$ must have total length at least $, \partial K, /2$, half the perimeter. One of the simplest involves the Crofton formula, according to which the length of any curve is proportional to its expected number of intersection points with a random line from an appropriate probability distribution on lines. It is convenient to simplify the problem by approximating $K$ by a strictly convex superset, which can be chosen to have perimeter arbitrarily close to the original set. Then, except for the tangent lines to $K$ (which form a vanishing fraction of all lines), a line that intersects $K$ crosses its boundary twice. Therefore, if a random line intersects $K$ with probability $p$, the expected number of boundary crossings is $2p$. But each line that intersects $K$ intersects its opaque set, so the expected number of intersections with the opaque set is at least $p$, which is at least half that for $K$. By the Crofton formula, the lengths of the boundary and barrier have the same proportion as these expected numbers.

This lower bound of $, \partial K, /2$ on the length of an opaque set cannot be improved to have a larger constant factor than 1/2, because there exist examples of convex sets that have opaque sets whose length is close to this lower bound. In particular, for very long thin rectangles, one long side and two short sides form a barrier, with total length that can be made arbitrarily close to half the perimeter. Therefore, among lower bounds that consider only the perimeter of the coverage region, the bound of $, \partial K, /2$ is best possible. However, getting closer to $, \partial K, /2$ in this way involves considering a sequence of shapes rather than just a single shape, because for any convex set $K$ that is not a triangle, there exists a $\delta$ such that all opaque sets have length at least $, \partial K, /2+\delta$.

Specific shapes

For a triangle, as for any convex polygon, the shortest connected opaque set is its minimum Steiner tree. In the case of a triangle, this tree can be described explicitly: if the widest angle of the triangle is $2\pi/3$ (120°) or more, it uses the two shortest edges of the triangle, and otherwise it consists of three line segments from the vertices to the Fermat point of the triangle. However, without assuming connectivity, the optimality of the Steiner tree has not been demonstrated. Izumi has proven a small improvement to the perimeter-halving lower bound for the equilateral triangle.

For a unit square, the perimeter is 4, the perimeter minus the longest edge is 3, and the length of the minimum Steiner tree is $1+\sqrt3\approx 2.732$. However, a shorter, disconnected opaque forest is known, with length $\sqrt2+\tfrac12\sqrt6\approx 2.639$. It consists of the minimum Steiner tree of three of the square's vertices, together with a line segment connecting the fourth vertex to the center. Ross Honsberger credits its discovery to Maurice Poirier, a Canadian schoolteacher, but it was already described in 1962 and 1964 by Jones. It is known to be optimal among forests with only two components, and has been conjectured to be the best possible more generally, but this remains unproven. The perimeter-halving lower bound of 2 for the square, already proven by Jones, can be improved slightly, to $2.00002$, for any barrier that consists of at most countably many rectifiable curves, improving similar previous bounds that constrained the barrier to be placed only near to the given square.

The case of the unit circle was described in a 1995 ''Scientific American'' column by Ian Stewart, with a solution of length $2+\pi$, optimal for a single curve or connected barrier but not for an opaque forest with multiple curves. Vance Faber and Jan Mycielski credit this single-curve solution to Menachem Magidor in 1974. By 1980, E. Makai had already provided a better three-component solution, with length approximately $4.7998$, rediscovered by John Day in a followup to Stewart's column. The unknown length of the optimal solution has been called the beam detection constant.

Algorithms

Two published algorithms claim to generate the optimal opaque forest for arbitrary polygons, based on the idea that the optimal solution has a special structure: a Steiner tree for one triangle in a triangulation of the polygon, and a segment in each remaining triangle from one vertex to the opposite side, of length equal to the height of the triangle. This structure matches the conjectured structure of the optimal solution for a square. Although the optimal triangulation for a solution of this form is not part of the input to these algorithms, it can be found by the algorithms in polynomial time using dynamic programming. However, these algorithms do not correctly solve the problem for all polygons, because some polygons have shorter solutions with a different structure than the ones they find. In particular, for a long thin rectangle, the minimum Steiner tree of all four vertices is shorter than the triangulation-based solution that these algorithms find. No known algorithm has been guaranteed to find a correct solution to the problem, regardless of its running time.

Despite this setback, the shortest single-curve barrier of a convex polygon, which is the traveling salesperson path of its vertices, can be computed exactly in polynomial time for convex polygons by a dynamic programming algorithm, in models of computation for which sums of radicals can be computed exactly. There has also been more successful study of approximation algorithms for the problem, and for determining the coverage of a given barrier.

Approximation

By the general bounds for opaque forest length in terms of perimeter, the perimeter of a convex set approximates its shortest opaque forest to within a factor of two in length. In two papers, Dumitrescu, Jiang, Pach, and Tóth provide several linear-time approximation algorithms for the shortest opaque set for convex polygons, with better approximation ratios than two:
*For general opaque sets, they provide an algorithm whose approximation ratio is at most $\frac+\frac\approx 1.5868.$ The general idea of the algorithm is to construct a "bow and arrow" like barrier from the minimum-perimeter bounding box of the input, consisting of a polygonal chain stretched around the polygon from one corner of the bounding box to the opposite corner, together with a line segment connecting a third corner of the bounding box to the diagonal of the box.
*For opaque sets consisting of a single arc, they provide an algorithm whose approximation ratio is at most $\frac\approx 1.5835.$ The resulting barrier is defined by a supporting line of the input shape. The input projects perpendicularly onto an interval of this line, and the barrier connects the two endpoints of this interval by a U-shaped curve stretched tight around the input, like the optimal connected barrier for a circle. The algorithm uses rotating calipers to find the supporting line for which the length of the resulting barrier is minimized.
*For connected opaque sets, they provide an algorithm whose approximation ratio is at most $1.5716$. This method combines the single-arc barrier with special treatment for shapes that are close to an equilateral triangle, for which the Steiner tree of the triangle is a shorter connected barrier.
*For interior barriers, they provide an algorithm whose approximation ratio is at most $1.7168$. The idea is to use a generalization suggested by Shermer of the structure of the incorrect earlier algorithms (a Steiner tree on a subset of the points, together with height segments for a triangulation of the remaining input), with a fast approximation for the Steiner tree part of the approximation.
Additionally, because the shortest connected interior barrier of a convex polygon is given by the minimum Steiner tree, it has a polynomial-time approximation scheme.

Coverage

The region covered by a given forest can be determined as follows:
*Find the convex hull of each connected component of the forest.
*For each vertex $p$ of the hull, sweep a line circularly around $p$, subdividing the plane into wedges within which the sweep line crosses one of the hulls and wedges within which the sweep line crosses the plane without obstruction. The union of the covered wedges forms a set $C_p$.
*Find the intersection of all of the sets $C_p$. This intersection is the coverage of the forest.
If the input consists of $n$ line segments forming $m$ connected components, then each of the $n$ sets $C_p$ consists of at most $2m$ wedges. It follows that the combinatorial complexity of the coverage region, and the time to construct it, is $O(m^2n^2)$ as expressed in big O notation.

Although optimal in the worst case for inputs whose coverage region has combinatorial complexity matching this bound, this algorithm can be improved heuristically in practice by a preprocessing phase that merges overlapping pairs of hulls until all remaining hulls are disjoint, in time $O(n\log^2 n)$. If this reduces the input to a single hull, the more expensive sweeping and intersecting algorithm need not be run: in this case the hull is the coverage region.

Curve-free opaque sets

showed that it is possible for an opaque set to avoid containing any nontrivial curves and still have finite total length. A simplified construction of , shown in the figure, produces an example for the unit square. The construction begins with line segments that form an opaque set with an additional property: the segments of negative slope block all lines of non-negative slope, while the segments of positive slope block all lines of non-positive slope. In the figure, the initial segments with this property are four disjoint segments along the diagonals of the square. Then, it repeatedly subdivides these segments while maintaining this property. At each level of the construction, each line segment is split by a small gap near its midpoint into two line segments, with slope of the same sign, that together block all lines of the opposite sign that were blocked by the original line segment. The limit set of this construction is a Cantor space that, like all intermediate stages of the construction, is an opaque set for the square. With quickly decreasing gap sizes, the construction produces a set whose Hausdorff dimension is one, and whose one-dimensional Hausdorff measure (a notion of length suitable for such sets) is finite.

The distance sets of the boundary of a square, or of the four-segment shortest known opaque set for the square, both contain all distances in the interval from 0 to $\sqrt$. However, by using similar fractal constructions, it is also possible to find fractal opaque sets whose distance sets omit infinitely many of the distances in this interval, or that (assuming the continuum hypothesis) form a set of measure zero.

History

Opaque sets were originally studied by Stefan Mazurkiewicz in 1916. Other early works on opaque sets include the papers of H. M. Sen Gupta and N. C. Basu Mazumdar in 1955, and by Frederick Bagemihl in 1959, but these are primarily about the distance sets and topological properties of barriers rather than about minimizing their length. In a postscript to his paper, Bagemihl asked for the minimum length of an interior barrier for the square, and subsequent work has largely focused on versions of the problem involving length minimization. They have been repeatedly posed, with multiple colorful formulations: digging a trench of as short a length as possible to find a straight buried telephone cable, trying to find a nearby straight road while lost in a forest, swimming to a straight shoreline while lost at sea, efficiently painting walls to render a glass house opaque, etc.

The problem has also been generalized to sets that block all geodesics on a Riemannian manifold, or that block lines through sets in higher-dimensions. In three dimensions, the corresponding question asks for a collection of surfaces of minimum total area that blocks all visibility across a solid. However, for some solids, such as a ball, it is not clear whether such a collection exists, or whether instead the area has an infimum that cannot be attained.

See also

* Bellman's lost in a forest problem
* Euclid's orchard

References

{{reflist, refs=

{{citation
, last = Akman , first = Varol
, doi = 10.1016/0020-0190(87)90185-2
, issue = 3
, journal = Information Processing Letters
, mr = 882227
, pages = 193–198
, title = An algorithm for determining an opaque minimal forest of a convex polygon
, volume = 24
, year = 1987, s2cid = 37582183

{{citation
, last = Bagemihl , first = F. , author-link = Frederick Bagemihl
, journal = Michigan Mathematical Journal
, mr = 105657
, pages = 99–103
, title = Some opaque subsets of a square
, url = https://projecteuclid.org/euclid.mmj/1028998183
, volume = 6
, year = 1959, issue = 2 , doi = 10.1307/mmj/1028998183

{{citation
, last1 = Beingessner , first1 = Alexis
, last2 = Smid , first2 = Michiel
, contribution = Computing the coverage of an opaque forest
, contribution-url = http://2012.cccg.ca/papers/paper53.pdf
, pages = 95–100
, title = Proc. 24th Canadian Conference on Computational Geometry (CCCG'12)
, year = 2012

{{citation
, last1 = Barba , first1 = Luis
, last2 = Beingessner , first2 = Alexis
, last3 = Bose , first3 = Prosenjit , author3-link = Jit Bose
, last4 = Smid , first4 = Michiel
, contribution = Computing covers of plane forests
, contribution-url = http://cccg.ca/proceedings/2013/papers/paper_18.pdf
, title = Proc. 25th Canadian Conference on Computational Geometry (CCCG'13)
, year = 2013

{{citation
, last = Brakke , first = Kenneth A.
, doi = 10.2307/2324127
, issue = 9
, journal = The American Mathematical Monthly
, jstor = 2324127
, mr = 1191707
, pages = 866–871
, title = The opaque cube problem
, volume = 99
, year = 1992

{{citation
, last = Croft , first = H. T.
, doi = 10.1112/jlms/s2-1.1.461
, journal = Journal of the London Mathematical Society
, mr = 247601
, pages = 461–469
, series = Second Series
, title = Curves intersecting certain sets of great-circles on the sphere
, volume = 1
, year = 1969

{{citation
, last1 = Dumitrescu , first1 = Adrian
, last2 = Jiang , first2 = Minghui
, arxiv = 1311.3323
, contribution = The opaque square
, doi = 10.1145/2582112.2582113
, location = New York
, mr = 3382335
, pages = 529–538
, publisher = Association for Computing Machinery
, s2cid = 207211457
, title = Proc. 30th Annual Symposium on Computational Geometry (SoCG'14)
, year = 2014

{{citation
, last1 = Dumitrescu , first1 = Adrian
, last2 = Jiang , first2 = Minghui
, last3 = Pach , first3 = János , author3-link = János Pach
, arxiv = 1005.2218
, doi = 10.1007/s00453-012-9735-2
, issue = 2
, journal = Algorithmica
, mr = 3183418
, pages = 315–334
, s2cid = 13884553
, title = Opaque sets
, volume = 69
, year = 2014

{{citation
, last1 = Dumitrescu , first1 = Adrian
, last2 = Jiang , first2 = Minghui
, last3 = Tóth , first3 = Csaba D.
, doi = 10.1137/14098805X
, issue = 3
, journal = SIAM Journal on Discrete Mathematics
, mr = 3376125
, pages = 1372–1386
, title = Computing opaque interior barriers à la Shermer
, volume = 29
, year = 2015, hdl = 10211.3/198469
, hdl-access = free

{{citation
, last = Dublish , first = Pratul
, doi = 10.1016/0020-0190(88)90122-6
, issue = 5
, journal = Information Processing Letters
, mr = 981078
, pages = 275–276
, title = An $O(n^3)$ algorithm for finding the minimal opaque forest of a convex polygon
, volume = 29
, year = 1988

{{citation
, last = Eggleston , first = H. G.
, doi = 10.1112/plms/s3-45.3.456
, issue = 3
, journal = Proceedings of the London Mathematical Society
, mr = 675417
, pages = 456–478
, series = Third Series
, title = The maximal inradius of the convex cover of a plane connected set of given length
, volume = 45
, year = 1982

{{citation
, last = Finch , first = Steven R.
, contribution = 8.11 Beam detection constant
, contribution-url = https://books.google.com/books?id=Pl5I2ZSI6uAC&pg=PA515
, isbn = 978-0-521-81805-6
, pages = 515–519
, publisher = Cambridge University Press
, series = Encyclopedia of Mathematics and its Applications
, title = Mathematical Constants
, year = 2003

{{citation
, last1 = Faber , first1 = V. , author1-link = Vance Faber
, last2 = Mycielski , first2 = J. , author2-link = Jan Mycielski
, doi = 10.2307/2322935
, issue = 10
, journal = The American Mathematical Monthly
, jstor = 2322935
, mr = 867106
, pages = 796–801
, title = The shortest curve that meets all the lines that meet a convex body
, volume = 93
, year = 1986

{{citation
, last1 = Sen Gupta , first1 = H. M. , author1-link = Hiranmay Sen Gupta
, last2 = Basu Mazumdar , first2 = N. C.
, journal = Bulletin of the Calcutta Mathematical Society
, mr = 80287
, pages = 199–201
, title = A note on certain plane sets of points
, volume = 47
, year = 1955

{{citation
, last = Honsberger , first = Ross , author-link = Ross Honsberger
, contribution = Problem 12: An opaque square
, isbn = 978-0-88385-303-0
, location = New York
, mr = 0490615
, pages = 22–25
, publisher = Mathematical Association of America
, series = The Dolciani Mathematical Expositions
, title = Mathematical Morsels
, volume = 3
, year = 1978

{{citation
, last = Izumi , first = Taisuke
, doi = 10.1016/j.dam.2016.05.006
, journal = Discrete Applied Mathematics
, mr = 3544574
, pages = 130–138
, title = Improving the lower bound on opaque sets for equilateral triangle
, volume = 213
, year = 2016, doi-access = free

{{citation
, last = Jones , first = Robert Edward Douglas
, contribution = Chapter 4: Opaque subsets of a square
, doi = 10.31274/rtd-180813-2223
, pages = 36–45
, publisher = Iowa State University
, series = Retrospective Theses and Dissertations
, title = Linear measure and opaque sets
, url = https://lib.dr.iastate.edu/rtd/2058
, volume = 2058
, year = 1962

{{citation
, last = Jones , first = R. E. D.
, doi = 10.2307/2312596
, journal = The American Mathematical Monthly
, jstor = 2312596
, mr = 164898
, pages = 535–537
, title = Opaque sets of degree $\alpha$
, volume = 71
, year = 1964

{{citation
, last = Joris , first = H.
, issue = 1
, journal = Elemente der Mathematik
, language = fr
, mr = 559167
, pages = 1–14
, title = Le chasseur perdu dans la forêt
, volume = 35
, year = 1980; translated into English by Steven Finch, {{arxiv, 1910.00615

{{citation
, last = Kawohl , first = Bernd
, editor1-last = Bandle , editor1-first = Catherine , editor1-link = Catherine Bandle
, editor2-last = Everitt , editor2-first = William N.
, editor3-last = Losonczi , editor3-first = Laszlo
, editor4-last = Walter , editor4-first = Wolfgang
, contribution = The opaque square and the opaque circle
, doi = 10.1007/978-3-0348-8942-1_27
, location = Basel
, mr = 1457290
, pages = 339–346
, publisher = Birkhäuser
, series = International Series of Numerical Mathematics
, title = General inequalities, 7 (Oberwolfach, 1995)
, volume = 123
, year = 1997

{{citation
, last = Kawohl , first = Bernd
, contribution = Some nonconvex shape optimization problems
, doi = 10.1007/BFb0106741
, mr = 1804684
, pages = 7–46
, publisher = Springer , location = Berlin
, series = Lecture Notes in Mathematics
, title = Optimal shape design (Tróia, 1998)
, volume = 1740
, year = 2000

{{citation
, last1 = Kawamura , first1 = Akitoshi
, last2 = Moriyama , first2 = Sonoko
, last3 = Otachi , first3 = Yota
, last4 = Pach , first4 = János , author4-link = János Pach
, doi = 10.1016/j.comgeo.2019.01.002
, journal = Computational Geometry
, mr = 3945133
, pages = 13–22
, title = A lower bound on opaque sets
, volume = 80
, year = 2019, url = http://real.mtak.hu/102414/1/10.1.1.757.5449.pdf

{{citation
, last = Mazurkiewicz , first = Stefan , authorlink = Stefan Mazurkiewicz
, journal = Prace Mat.-Fiz.
, language = Polish, French
, pages = 11–16
, title = Sur un ensemble fermé, punctiforme, qui rencontre toute droite passant par un certain domaine
, volume = 27
, year = 1916

{{citation
, last = Makai , first = E. Jr.
, contribution = On a dual of Tarski's plank problem
, pages = 127–132
, publisher = Inst. Math. Univ. Salzburg
, title = 2nd Colloquium on Discrete Geometry
, year = 1980
, zbl = 459.52005

{{citation
, last1 = Asimov , first1 = Daniel
, last2 = Gerver , first2 = Joseph L.
, doi = 10.1007/s10711-008-9234-4
, journal = Geometriae Dedicata
, mr = 2390069
, pages = 67–82
, title = Minimum opaque manifolds
, volume = 133
, year = 2008, s2cid = 122556952

{{citation
, last = Nahin , first = Paul J.
, contribution = Chapter 7: The Modern Age Begins
, doi = 10.2307/j.ctv19qmf43.12
, jstor = j.ctv19qmf43.12
, pages = 279–330
, publisher = Princeton University Press
, title = When Least Is Best: How Mathematicians Discovered Many Clever Ways to Make Things as Small (or as Large) as Possible
, year = 2021

{{citation
, last1 = Provan , first1 = J. Scott
, last2 = Brazil , first2 = Marcus
, last3 = Thomas , first3 = Doreen
, authorlink3 = Doreen Thomas
, last4 = Weng , first4 = Jia F.
, arxiv = 1210.8139 , bibcode = 2012arXiv1210.8139P
, title = Minimum opaque covers for polygonal regions
, year = 2012

{{citation
, last = Shermer , first = Thomas
, doi = 10.1016/S0020-0190(05)80008-0
, issue = 1
, journal = Information Processing Letters
, mr = 1134007
, pages = 41–42
, title = A counterexample to the algorithms for determining opaque minimal forests
, volume = 40
, year = 1991

{{citation
, last = Smart , first = J. R.
, date = April 1966
, doi = 10.2307/2315418
, issue = 4
, journal = The American Mathematical Monthly
, jstor = 2315418
, pages = 401–409
, title = Searching for mathematical Talent in Wisconsin, II
, volume = 73; see Problem set 4, problem 5, p. 405

{{citation
, last = Stewart , first = Ian , author-link = Ian Stewart (mathematician)
, date = September 1995
, issue = 3
, journal = Scientific American
, jstor = 24981805
, pages = 206–207
, title = The great drain robbery
, volume = 273, doi = 10.1038/scientificamerican0995-206 , bibcode = 1995SciAm.273c.206S

{{citation
, last = Stewart , first = Ian , author-link = Ian Stewart (mathematician)
, date = February 1996
, issue = 2
, journal = Scientific American
, jstor = 24989406
, page = 125
, title = Feedback
, volume = 274

Discrete geometry
Visibility