2308:, 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
33:
1727:. 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.
1575:
2290:
2384:
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.
1719:, 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
2395:, 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
1944:. 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.
2383:
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
1210:
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,
901:
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
2235:
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
1546:
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
1889:
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
702:, 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
1754:
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
872:
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
1823:
2011:, 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
1540:
245:
130:
1427:
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
1715:
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
1883:
2355:. 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
1392:, 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
255:
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
1833:
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.
247:. 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
1488:
78:
1378:
1211:
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
765:, 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.
2279:
1625:
1291:
1250:
1208:
973:
2226:
850:
2353:
817:
3366:
3001:
1565:
1421:
1331:
1942:
1915:
1701:
1669:
1602:
327:
287:
2281:. 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.
2157:
2066:
2036:
307:
3130:
2316:
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
2180:
1770:
1730:
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
1104:
3544:
2130:
2110:
2090:
2009:
1989:
1311:
1164:
1144:
1124:
1081:
1061:
1041:
1021:
1001:
932:
870:
791:
747:
723:
692:
660:
629:
609:
577:
557:
521:
501:
481:
461:
441:
421:
398:
378:
3609:
2304:
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
1542:. 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.
1444:
2331:
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
1003:
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
979:, according to which the length of any curve is proportional to its expected number of intersection points with a random line from an appropriate
3273:
2926:
2408:
1839:
3448:
1949:
1423:(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
1493:
198:
83:
2918:
195:
can be blocked by its four boundary edges, with length 4, but a shorter opaque forest blocks visibility across the square with length
3689:
3572:
3005:
2796:
3052:
674:
without changing its opaque sets. Some variants of the problem restrict the opaque set to lie entirely inside or entirely outside
2744:
1948:
Additionally, because the shortest connected interior barrier of a convex polygon is given by the minimum
Steiner tree, it has a
3409:
3370:
3290:
1703:, rediscovered by John Day in a followup to Stewart's column. The unknown length of the optimal solution has been called the
2478:
2874:
3225:
3081:
1642:
1166:. By the Crofton formula, the lengths of the boundary and barrier have the same proportion as these expected numbers.
894:
2840:
When Least Is Best: How
Mathematicians Discovered Many Clever Ways to Make Things as Small (or as Large) as Possible
3737:
3265:
2843:
1293:
in this way involves considering a sequence of shapes rather than just a single shape, because for any convex set
1457:
47:
1454:, the perimeter is 4, the perimeter minus the longest edge is 3, and the length of the minimum Steiner tree is
980:
3446:
Dumitrescu, Adrian; Jiang, Minghui; Tóth, Csaba D. (2015), "Computing opaque interior barriers à la
Shermer",
3128:
Eggleston, H. G. (1982), "The maximal inradius of the convex cover of a plane connected set of given length",
2182:
wedges. It follows that the combinatorial complexity of the coverage region, and the time to construct it, is
877:
through it that cannot be blocked by any other points. The same reasoning shows that for interior barriers of
749:
can be approximated arbitrarily closely in length by an opaque forest, and it has been conjectured that every
1683:
in 1974. By 1980, E. Makai had already provided a better three-component solution, with length approximately
1571:, improving similar previous bounds that constrained the barrier to be placed only near to the given square.
3169:
1825:
The general idea of the algorithm is to construct a "bow and arrow" like barrier from the minimum-perimeter
1743:
1336:
1836:
For opaque sets consisting of a single arc, they provide an algorithm whose approximation ratio is at most
348:, or to compute the subset of the plane whose visibility is blocked by a given system of line segments in
2441:(1916), "Sur un ensemble fermé, punctiforme, qui rencontre toute droite passant par un certain domaine",
1547:
perimeter-halving lower bound of 2 for the square, already proven by Jones, can be improved slightly, to
2959:
1716:
584:
169:
32:
639:
can be used, and agrees with the standard length in the cases of line segments and rectifiable curves.
340:
were later shown to be incorrect. Nevertheless, it is possible to find an opaque set with a guaranteed
3407:
Shermer, Thomas (1991), "A counterexample to the algorithms for determining opaque minimal forests",
3095:
2540:
2356:
1918:
1917:. This method combines the single-arc barrier with special treatment for shapes that are close to an
1671:, optimal for a single curve or connected barrier but not for an opaque forest with multiple curves.
1428:
886:
289:. Without the assumption of connectivity, the shortest opaque set for the circle has length at least
2239:
1607:
1255:
1214:
1172:
937:
3742:
3645:
3230:
3086:
2438:
2413:
2392:
2372:
2317:
2185:
1760:
1735:
1724:
1637:
1126:
intersects its opaque set, so the expected number of intersections with the opaque set is at least
794:
341:
181:
3288:
Akman, Varol (1987), "An algorithm for determining an opaque minimal forest of a convex polygon",
822:
3706:
3670:
3589:
3539:
3315:
3239:
3187:
3111:
3022:
2855:
2813:
2709:
2683:
2615:
2589:
2530:
2469:
2380:
2376:
2334:
635:, their length can be measured in the standard way. For more general point sets, one-dimensional
185:
799:
725:
has a shortest opaque set, or whether instead the lengths of its opaque sets might approach an
631:
itself, and many possible opaque forests. For opaque forests, or more generally for systems of
3335:
3269:
3257:
2922:
2321:
1891:
882:
852:. Therefore, the shortest possible length of an opaque set is at most the perimeter. For sets
636:
137:
2986:
1550:
1395:
1316:
3698:
3654:
3618:
3581:
3465:
3457:
3418:
3379:
3299:
3208:
3139:
3103:
3056:
3014:
2963:
2883:
2872:
Izumi, Taisuke (2016), "Improving the lower bound on opaque sets for equilateral triangle",
2847:
2805:
2753:
2693:
2648:
2636:
2599:
2487:
1927:
1900:
1686:
1680:
1648:
1581:
1578:
Opaque forests for a unit circle. Left: the U-shaped optimal connected barrier, with length
312:
266:
145:
3718:
3666:
3630:
3557:
3479:
3430:
3391:
3311:
3182:
3151:
3068:
3034:
2936:
2897:
2825:
2765:
2705:
2660:
2611:
2499:
2135:
2044:
2014:
3714:
3662:
3626:
3553:
3475:
3426:
3387:
3307:
3178:
3147:
3064:
3030:
2932:
2910:
2893:
2821:
2761:
2701:
2656:
2607:
2495:
1897:
For connected opaque sets, they provide an algorithm whose approximation ratio is at most
1886:
1830:
1739:
1731:
1720:
1568:
1543:
976:
632:
349:
292:
3212:
3607:
Croft, H. T. (1969), "Curves intersecting certain sets of great-circles on the sphere",
3099:
2544:
2162:
1767:
For general opaque sets, they provide an algorithm whose approximation ratio is at most
1574:
1086:
40:. Upper left: its boundary, length 4. Upper right: Three sides, length 3. Lower left: a
3107:
2229:
2115:
2095:
2075:
1994:
1974:
1894:
to find the supporting line for which the length of the resulting barrier is minimized.
1296:
1149:
1129:
1109:
1066:
1046:
1026:
1006:
986:
917:
878:
855:
776:
750:
732:
708:
677:
645:
614:
594:
562:
542:
506:
486:
466:
446:
426:
406:
383:
363:
337:
3519:
3422:
1924:
For interior barriers, they provide an algorithm whose approximation ratio is at most
1759:
approximation algorithms for the shortest opaque set for convex polygons, with better
3731:
3674:
3383:
3303:
2791:
2732:
2713:
2644:
2575:
2522:
1676:
667:
260:
17:
3319:
2619:
2736:
2580:
2328:
2313:
1826:
1424:
874:
580:
173:
41:
2473:
2289:
3570:
Smart, J. R. (April 1966), "Searching for mathematical Talent in
Wisconsin, II",
2757:
2652:
2787:
1965:
1756:
1672:
1632:
1451:
903:
671:
345:
256:
192:
37:
3143:
2859:
2794:(1986), "The shortest curve that meets all the lines that meet a convex body",
753:
has an opaque forest as its shortest opaque set, but this has not been proven.
3658:
3622:
2952:
Jones, Robert Edward
Douglas (1962), "Chapter 4: Opaque subsets of a square",
2888:
2603:
762:
703:
663:
248:
2967:
2491:
2851:
2697:
2309:
1921:, for which the Steiner tree of the triangle is a shorter connected barrier.
333:
252:
149:
1818:{\displaystyle {\frac {1}{2}}+{\frac {2+{\sqrt {2}}}{\pi }}\approx 1.5868.}
3470:
3542:; Basu Mazumdar, N. C. (1955), "A note on certain plane sets of points",
3515:
3493:
2388:
2360:
1389:
3243:
3115:
3710:
3593:
3060:
3026:
2817:
2643:, International Series of Numerical Mathematics, vol. 123, Basel:
2396:
2294:
1746:
for the problem, and for determining the coverage of a given barrier.
1490:. However, a shorter, disconnected opaque forest is known, with length
1433:
1023:(which form a vanishing fraction of all lines), a line that intersects
726:
184:
in 1916, and the problem of minimizing their total length was posed by
153:
3643:
Asimov, Daniel; Gerver, Joseph L. (2008), "Minimum opaque manifolds",
3461:
3368:
algorithm for finding the minimal opaque forest of a convex polygon",
2953:
1742:
can be computed exactly. There has also been more successful study of
1441:
What are the shortest opaque sets for the unit square and unit circle?
3702:
3585:
3047:
Kawohl, Bernd (2000), "Some nonconvex shape optimization problems",
3018:
2809:
2635:
Kawohl, Bernd (1997), "The opaque square and the opaque circle", in
983:
on lines. It is convenient to simplify the problem by approximating
3191:
2682:, New York: Association for Computing Machinery, pp. 529–538,
1960:
The region covered by a given forest can be determined as follows:
1535:{\displaystyle {\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639}
1043:
crosses its boundary twice. Therefore, if a random line intersects
443:
consists of points for which all lines through the point intersect
240:{\displaystyle {\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639}
125:{\displaystyle {\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639}
3527:
Proc. 25th
Canadian Conference on Computational Geometry (CCCG'13)
3501:
Proc. 24th
Canadian Conference on Computational Geometry (CCCG'12)
2688:
2639:; Everitt, William N.; Losonczi, Laszlo; Walter, Wolfgang (eds.),
2594:
2535:
2288:
1604:. Right: The best barrier known, with three components and length
1573:
31:
2917:, The Dolciani Mathematical Expositions, vol. 3, New York:
2678:
Dumitrescu, Adrian; Jiang, Minghui (2014), "The opaque square",
2375:
in 1916. Other early works on opaque sets include the papers of
2680:
Proc. 30th Annual Symposium on Computational Geometry (SoCG'14)
914:
There are several proofs that an opaque set for any convex set
3203:
Makai, E. Jr. (1980), "On a dual of Tarski's plank problem",
2387:
The problem has also been generalized to sets that block all
156:, circle, or other shape. Opaque sets have also been called
2838:
Nahin, Paul J. (2021), "Chapter 7: The Modern Age Begins",
2958:, Retrospective Theses and Dissertations, vol. 2058,
1567:, for any barrier that consists of at most countably many
642:
Most research on this problem assumes that the given set
380:
in the plane blocks the visibility through a superset of
3051:, Lecture Notes in Mathematics, vol. 1740, Berlin:
2293:
The first four stages of a construction by Bagemihl for
591:. There are many possible opaque sets for any given set
80:. Lower right: the conjectured optimal solution, length
2324:(a notion of length suitable for such sets) is finite.
1878:{\displaystyle {\frac {\pi +5}{\pi +2}}\approx 1.5835.}
975:, half the perimeter. One of the simplest involves the
3687:
Brakke, Kenneth A. (1992), "The opaque cube problem",
1508:
213:
98:
3338:
3167:
Joris, H. (1980), "Le chasseur perdu dans la forêt",
2989:
2337:
2242:
2188:
2165:
2138:
2118:
2098:
2078:
2047:
2017:
1997:
1977:
1930:
1903:
1842:
1773:
1689:
1651:
1610:
1584:
1553:
1496:
1460:
1398:
1339:
1319:
1299:
1258:
1217:
1175:
1152:
1132:
1112:
1089:
1069:
1049:
1029:
1009:
989:
940:
920:
858:
825:
802:
779:
735:
711:
680:
648:
617:
597:
565:
545:
509:
489:
469:
449:
429:
409:
386:
366:
315:
295:
269:
201:
86:
50:
3264:, Encyclopedia of Mathematics and its Applications,
2731:
Kawamura, Akitoshi; Moriyama, Sonoko; Otachi, Yota;
3360:
2995:
2347:
2273:
2220:
2174:
2151:
2124:
2104:
2084:
2068:. This intersection is the coverage of the forest.
2060:
2030:
2003:
1983:
1936:
1909:
1877:
1817:
1695:
1663:
1619:
1596:
1559:
1534:
1482:
1415:
1372:
1325:
1305:
1285:
1244:
1202:
1158:
1138:
1118:
1098:
1075:
1055:
1035:
1015:
995:
967:
926:
864:
844:
819:forms an opaque set whose length is the perimeter
811:
785:
741:
717:
686:
654:
623:
603:
571:
551:
515:
495:
475:
455:
435:
415:
392:
372:
321:
301:
281:
239:
124:
72:
3207:, Inst. Math. Univ. Salzburg, pp. 127–132,
793:is a bounded convex set to be covered, then its
579:has a special form, consisting of finitely many
2983:Jones, R. E. D. (1964), "Opaque sets of degree
1333:such that all opaque sets have length at least
1083:, the expected number of boundary crossings is
729:without ever reaching it. Every opaque set for
336:claiming to find the shortest opaque set for a
3131:Proceedings of the London Mathematical Society
1738:algorithm, in models of computation for which
3545:Bulletin of the Calcutta Mathematical Society
3084:(September 1995), "The great drain robbery",
1252:is best possible. However, getting closer to
168:, or (in cases where they have the form of a
8:
3494:"Computing the coverage of an opaque forest"
2301:
1991:of the hull, sweep a line circularly around
902:perimeter or Steiner tree length provide an
3492:Beingessner, Alexis; Smid, Michiel (2012),
3186:; translated into English by Steven Finch,
2641:General inequalities, 7 (Oberwolfach, 1995)
2527:Minimum opaque covers for polygonal regions
3610:Journal of the London Mathematical Society
3402:
3400:
2978:
2976:
2947:
2945:
1968:of each connected component of the forest.
1483:{\displaystyle 1+{\sqrt {3}}\approx 2.732}
144:is a system of curves or other set in the
73:{\displaystyle 1+{\sqrt {3}}\approx 2.732}
3469:
3349:
3337:
2988:
2887:
2687:
2593:
2534:
2338:
2336:
2256:
2241:
2209:
2199:
2187:
2164:
2143:
2137:
2117:
2097:
2077:
2052:
2046:
2041:Find the intersection of all of the sets
2022:
2016:
1996:
1976:
1929:
1902:
1843:
1841:
1796:
1787:
1774:
1772:
1688:
1650:
1609:
1583:
1552:
1519:
1507:
1497:
1495:
1467:
1459:
1405:
1397:
1356:
1351:
1340:
1338:
1318:
1298:
1275:
1270:
1259:
1257:
1234:
1229:
1218:
1216:
1192:
1187:
1176:
1174:
1151:
1131:
1111:
1088:
1068:
1048:
1028:
1008:
988:
957:
952:
941:
939:
919:
857:
837:
826:
824:
801:
778:
734:
710:
679:
647:
616:
596:
564:
544:
508:
488:
468:
448:
428:
408:
385:
365:
314:
294:
268:
224:
212:
202:
200:
109:
97:
87:
85:
57:
49:
3162:
3160:
2913:(1978), "Problem 12: An opaque square",
2379:and N. C. Basu Mazumdar in 1955, and by
2305:
2425:
2371:Opaque sets were originally studied by
2112:connected components, then each of the
1445:(more unsolved problems in mathematics)
1313:that is not a triangle, there exists a
3597:; see Problem set 4, problem 5, p. 405
3441:
3439:
2782:
2780:
2778:
2776:
2774:
2726:
2724:
2722:
2516:
2514:
2512:
2510:
2508:
1885:The resulting barrier is defined by a
1373:{\displaystyle |\partial K|/2+\delta }
2630:
2628:
2569:
2567:
2565:
2563:
2561:
2559:
2557:
2555:
2553:
2464:
2462:
2460:
2458:
2456:
2433:
2431:
2429:
1679:credit this single-curve solution to
666:. When it is not convex but merely a
7:
3449:SIAM Journal on Discrete Mathematics
2673:
2671:
2669:
2574:Dumitrescu, Adrian; Jiang, Minghui;
1950:polynomial-time approximation scheme
251:in the plane has length at most the
29:Shape that blocks all lines of sight
3520:"Computing covers of plane forests"
3205:2nd Colloquium on Discrete Geometry
2919:Mathematical Association of America
761:When the region to be covered is a
191:For instance, visibility through a
3514:Barba, Luis; Beingessner, Alexis;
3108:10.1038/scientificamerican0995-206
3049:Optimal shape design (Tróia, 1998)
2521:Provan, J. Scott; Brazil, Marcus;
2409:Bellman's lost in a forest problem
2320:is one, and whose one-dimensional
1345:
1264:
1223:
1181:
1146:, which is at least half that for
946:
831:
803:
483:forms a subset of the coverage of
25:
3690:The American Mathematical Monthly
3573:The American Mathematical Monthly
3006:The American Mathematical Monthly
2797:The American Mathematical Monthly
2474:"Some opaque subsets of a square"
885:must be included. Therefore, the
180:. Opaque sets were introduced by
1106:. But each line that intersects
934:must have total length at least
906:on the length of an opaque set.
897:of the vertices is the shortest
889:of the vertices is the shortest
694:. In this case, it is called an
2297:opaque sets for the unit square
1436:Unsolved problem in mathematics
3410:Information Processing Letters
3371:Information Processing Letters
3355:
3342:
3291:Information Processing Letters
3258:"8.11 Beam detection constant"
2955:Linear measure and opaque sets
2737:"A lower bound on opaque sets"
2274:{\displaystyle O(n\log ^{2}n)}
2268:
2246:
2215:
2192:
1829:of the input, consisting of a
1620:{\displaystyle \approx 4.7998}
1352:
1341:
1286:{\displaystyle |\partial K|/2}
1271:
1260:
1245:{\displaystyle |\partial K|/2}
1230:
1219:
1203:{\displaystyle |\partial K|/2}
1188:
1177:
968:{\displaystyle |\partial K|/2}
953:
942:
838:
827:
1:
3423:10.1016/S0020-0190(05)80008-0
3228:(February 1996), "Feedback",
2479:Michigan Mathematical Journal
2221:{\displaystyle O(m^{2}n^{2})}
3384:10.1016/0020-0190(88)90122-6
3332:Dublish, Pratul (1988), "An
3304:10.1016/0020-0190(87)90185-2
2875:Discrete Applied Mathematics
2758:10.1016/j.comgeo.2019.01.002
2653:10.1007/978-3-0348-8942-1_27
1717:triangulation of the polygon
1645:, with a solution of length
845:{\displaystyle |\partial K|}
670:, it can be replaced by its
2348:{\displaystyle {\sqrt {2}}}
3759:
3266:Cambridge University Press
2844:Princeton University Press
2312:of this construction is a
895:traveling salesperson path
812:{\displaystyle \partial K}
3659:10.1007/s10711-008-9234-4
3256:Finch, Steven R. (2003),
2889:10.1016/j.dam.2016.05.006
2604:10.1007/s00453-012-9735-2
2399:that cannot be attained.
2072:If the input consists of
1734:for convex polygons by a
259:, for which the shortest
3518:; Smid, Michiel (2013),
3361:{\displaystyle O(n^{3})}
3144:10.1112/plms/s3-45.3.456
2968:10.31274/rtd-180813-2223
2445:(in Polish and French),
1744:approximation algorithms
1635:was described in a 1995
981:probability distribution
44:of the vertices, length
3623:10.1112/jlms/s2-1.1.461
3170:Elemente der Mathematik
2996:{\displaystyle \alpha }
2852:10.2307/j.ctv19qmf43.12
2698:10.1145/2582112.2582113
2578:(2014), "Opaque sets",
2525:; Weng, Jia F. (2012),
1705:beam detection constant
1560:{\displaystyle 2.00002}
1416:{\displaystyle 2\pi /3}
1326:{\displaystyle \delta }
36:Four opaque sets for a
3362:
3262:Mathematical Constants
2997:
2745:Computational Geometry
2492:10.1307/mmj/1028998183
2349:
2298:
2285:Curve-free opaque sets
2275:
2222:
2176:
2153:
2126:
2106:
2092:line segments forming
2086:
2062:
2032:
2005:
1985:
1938:
1937:{\displaystyle 1.7168}
1911:
1910:{\displaystyle 1.5716}
1879:
1819:
1697:
1696:{\displaystyle 4.7998}
1665:
1664:{\displaystyle 2+\pi }
1628:
1621:
1598:
1597:{\displaystyle 2+\pi }
1561:
1536:
1484:
1417:
1374:
1327:
1307:
1287:
1246:
1204:
1160:
1140:
1120:
1100:
1077:
1057:
1037:
1017:
997:
969:
928:
866:
846:
813:
787:
743:
719:
688:
656:
625:
605:
573:
553:
517:
497:
477:
457:
437:
417:
394:
374:
323:
322:{\displaystyle 4.7998}
303:
283:
282:{\displaystyle 2+\pi }
263:opaque set has length
241:
133:
126:
74:
3363:
2998:
2960:Iowa State University
2350:
2292:
2276:
2223:
2177:
2154:
2152:{\displaystyle C_{p}}
2127:
2107:
2087:
2063:
2061:{\displaystyle C_{p}}
2033:
2031:{\displaystyle C_{p}}
2006:
1986:
1939:
1912:
1880:
1820:
1698:
1666:
1622:
1599:
1577:
1562:
1537:
1485:
1418:
1375:
1328:
1308:
1288:
1247:
1205:
1161:
1141:
1121:
1101:
1078:
1058:
1038:
1018:
998:
970:
929:
867:
847:
814:
788:
744:
720:
689:
657:
626:
606:
574:
554:
518:
498:
478:
458:
438:
418:
395:
375:
324:
304:
284:
242:
127:
75:
35:
18:Opaque forest problem
3336:
3268:, pp. 515–519,
2987:
2915:Mathematical Morsels
2846:, pp. 279–330,
2647:, pp. 339–346,
2439:Mazurkiewicz, Stefan
2357:continuum hypothesis
2335:
2240:
2186:
2163:
2159:consists of at most
2136:
2116:
2096:
2076:
2045:
2015:
1995:
1975:
1928:
1919:equilateral triangle
1901:
1840:
1771:
1761:approximation ratios
1687:
1649:
1608:
1582:
1551:
1494:
1458:
1429:equilateral triangle
1396:
1337:
1317:
1297:
1256:
1215:
1173:
1169:This lower bound of
1150:
1130:
1110:
1087:
1067:
1047:
1027:
1007:
987:
938:
918:
893:opaque set, and the
887:minimum Steiner tree
856:
823:
800:
777:
733:
709:
678:
646:
615:
595:
583:whose union forms a
563:
559:. If, additionally,
543:
507:
487:
467:
447:
427:
407:
384:
364:
313:
302:{\displaystyle \pi }
293:
267:
199:
84:
48:
3646:Geometriae Dedicata
3231:Scientific American
3100:1995SciAm.273c.206S
3087:Scientific American
2545:2012arXiv1210.8139P
2393:Riemannian manifold
2373:Stefan Mazurkiewicz
2361:set of measure zero
2318:Hausdorff dimension
2302:Mazurkiewicz (1916)
1736:dynamic programming
1725:dynamic programming
1638:Scientific American
342:approximation ratio
182:Stefan Mazurkiewicz
3358:
3061:10.1007/BFb0106741
2993:
2962:, pp. 36–45,
2921:, pp. 22–25,
2381:Frederick Bagemihl
2345:
2299:
2271:
2218:
2175:{\displaystyle 2m}
2172:
2149:
2122:
2102:
2082:
2058:
2028:
2001:
1981:
1934:
1907:
1875:
1815:
1693:
1661:
1629:
1617:
1594:
1569:rectifiable curves
1557:
1532:
1517:
1480:
1413:
1370:
1323:
1303:
1283:
1242:
1200:
1156:
1136:
1116:
1099:{\displaystyle 2p}
1096:
1073:
1053:
1033:
1013:
993:
965:
924:
862:
842:
809:
783:
739:
715:
684:
652:
633:rectifiable curves
621:
601:
587:, it is called an
569:
549:
513:
493:
473:
453:
433:
413:
390:
370:
332:Several published
319:
299:
279:
237:
222:
186:Frederick Bagemihl
134:
122:
107:
70:
3738:Discrete geometry
3613:, Second Series,
3503:, pp. 95–100
3462:10.1137/14098805X
3275:978-0-521-81805-6
3055:, pp. 7–46,
2928:978-0-88385-303-0
2637:Bandle, Catherine
2343:
2322:Hausdorff measure
2125:{\displaystyle n}
2105:{\displaystyle m}
2085:{\displaystyle n}
2004:{\displaystyle p}
1984:{\displaystyle p}
1892:rotating calipers
1867:
1807:
1801:
1782:
1524:
1516:
1502:
1472:
1306:{\displaystyle K}
1159:{\displaystyle K}
1139:{\displaystyle p}
1119:{\displaystyle K}
1076:{\displaystyle p}
1063:with probability
1056:{\displaystyle K}
1036:{\displaystyle K}
1016:{\displaystyle K}
996:{\displaystyle K}
927:{\displaystyle K}
865:{\displaystyle K}
786:{\displaystyle K}
742:{\displaystyle P}
718:{\displaystyle P}
687:{\displaystyle K}
655:{\displaystyle K}
637:Hausdorff measure
624:{\displaystyle K}
604:{\displaystyle K}
572:{\displaystyle S}
552:{\displaystyle K}
523:is said to be an
516:{\displaystyle S}
496:{\displaystyle S}
476:{\displaystyle K}
463:. If a given set
456:{\displaystyle S}
436:{\displaystyle C}
416:{\displaystyle C}
393:{\displaystyle S}
373:{\displaystyle S}
229:
221:
207:
176:or other curves)
138:discrete geometry
114:
106:
92:
62:
16:(Redirected from
3750:
3722:
3721:
3684:
3678:
3677:
3640:
3634:
3633:
3604:
3598:
3596:
3567:
3561:
3560:
3540:Sen Gupta, H. M.
3536:
3530:
3529:
3524:
3511:
3505:
3504:
3498:
3489:
3483:
3482:
3473:
3456:(3): 1372–1386,
3443:
3434:
3433:
3404:
3395:
3394:
3367:
3365:
3364:
3359:
3354:
3353:
3329:
3323:
3322:
3285:
3279:
3278:
3253:
3247:
3246:
3222:
3216:
3215:
3200:
3194:
3185:
3164:
3155:
3154:
3134:, Third Series,
3125:
3119:
3118:
3078:
3072:
3071:
3044:
3038:
3037:
3002:
3000:
2999:
2994:
2980:
2971:
2970:
2949:
2940:
2939:
2911:Honsberger, Ross
2907:
2901:
2900:
2891:
2869:
2863:
2862:
2835:
2829:
2828:
2784:
2769:
2768:
2741:
2728:
2717:
2716:
2691:
2675:
2664:
2663:
2632:
2623:
2622:
2597:
2571:
2548:
2547:
2538:
2518:
2503:
2502:
2466:
2451:
2450:
2435:
2414:Euclid's orchard
2354:
2352:
2351:
2346:
2344:
2339:
2280:
2278:
2277:
2272:
2261:
2260:
2228:as expressed in
2227:
2225:
2224:
2219:
2214:
2213:
2204:
2203:
2181:
2179:
2178:
2173:
2158:
2156:
2155:
2150:
2148:
2147:
2131:
2129:
2128:
2123:
2111:
2109:
2108:
2103:
2091:
2089:
2088:
2083:
2067:
2065:
2064:
2059:
2057:
2056:
2037:
2035:
2034:
2029:
2027:
2026:
2010:
2008:
2007:
2002:
1990:
1988:
1987:
1982:
1971:For each vertex
1943:
1941:
1940:
1935:
1916:
1914:
1913:
1908:
1884:
1882:
1881:
1876:
1868:
1866:
1855:
1844:
1824:
1822:
1821:
1816:
1808:
1803:
1802:
1797:
1788:
1783:
1775:
1740:sums of radicals
1702:
1700:
1699:
1694:
1681:Menachem Magidor
1670:
1668:
1667:
1662:
1631:The case of the
1626:
1624:
1623:
1618:
1603:
1601:
1600:
1595:
1566:
1564:
1563:
1558:
1541:
1539:
1538:
1533:
1525:
1520:
1518:
1509:
1503:
1498:
1489:
1487:
1486:
1481:
1473:
1468:
1437:
1422:
1420:
1419:
1414:
1409:
1379:
1377:
1376:
1371:
1360:
1355:
1344:
1332:
1330:
1329:
1324:
1312:
1310:
1309:
1304:
1292:
1290:
1289:
1284:
1279:
1274:
1263:
1251:
1249:
1248:
1243:
1238:
1233:
1222:
1209:
1207:
1206:
1201:
1196:
1191:
1180:
1165:
1163:
1162:
1157:
1145:
1143:
1142:
1137:
1125:
1123:
1122:
1117:
1105:
1103:
1102:
1097:
1082:
1080:
1079:
1074:
1062:
1060:
1059:
1054:
1042:
1040:
1039:
1034:
1022:
1020:
1019:
1014:
1002:
1000:
999:
994:
974:
972:
971:
966:
961:
956:
945:
933:
931:
930:
925:
871:
869:
868:
863:
851:
849:
848:
843:
841:
830:
818:
816:
815:
810:
792:
790:
789:
784:
748:
746:
745:
740:
724:
722:
721:
716:
700:exterior barrier
696:interior barrier
693:
691:
690:
685:
661:
659:
658:
653:
630:
628:
627:
622:
610:
608:
607:
602:
578:
576:
575:
570:
558:
556:
555:
550:
522:
520:
519:
514:
502:
500:
499:
494:
482:
480:
479:
474:
462:
460:
459:
454:
442:
440:
439:
434:
422:
420:
419:
414:
399:
397:
396:
391:
379:
377:
376:
371:
328:
326:
325:
320:
308:
306:
305:
300:
288:
286:
285:
280:
246:
244:
243:
238:
230:
225:
223:
214:
208:
203:
148:that blocks all
131:
129:
128:
123:
115:
110:
108:
99:
93:
88:
79:
77:
76:
71:
63:
58:
21:
3758:
3757:
3753:
3752:
3751:
3749:
3748:
3747:
3728:
3727:
3726:
3725:
3703:10.2307/2324127
3686:
3685:
3681:
3642:
3641:
3637:
3606:
3605:
3601:
3586:10.2307/2315418
3569:
3568:
3564:
3538:
3537:
3533:
3522:
3516:Bose, Prosenjit
3513:
3512:
3508:
3496:
3491:
3490:
3486:
3445:
3444:
3437:
3406:
3405:
3398:
3345:
3334:
3333:
3331:
3330:
3326:
3287:
3286:
3282:
3276:
3255:
3254:
3250:
3224:
3223:
3219:
3202:
3201:
3197:
3166:
3165:
3158:
3127:
3126:
3122:
3080:
3079:
3075:
3046:
3045:
3041:
3019:10.2307/2312596
2985:
2984:
2982:
2981:
2974:
2951:
2950:
2943:
2929:
2909:
2908:
2904:
2871:
2870:
2866:
2860:j.ctv19qmf43.12
2837:
2836:
2832:
2810:10.2307/2322935
2804:(10): 796–801,
2786:
2785:
2772:
2739:
2730:
2729:
2720:
2677:
2676:
2667:
2634:
2633:
2626:
2573:
2572:
2551:
2520:
2519:
2506:
2468:
2467:
2454:
2443:Prace Mat.-Fiz.
2437:
2436:
2427:
2422:
2405:
2377:H. M. Sen Gupta
2369:
2333:
2332:
2306:Bagemihl (1959)
2287:
2252:
2238:
2237:
2205:
2195:
2184:
2183:
2161:
2160:
2139:
2134:
2133:
2114:
2113:
2094:
2093:
2074:
2073:
2048:
2043:
2042:
2018:
2013:
2012:
1993:
1992:
1973:
1972:
1958:
1926:
1925:
1899:
1898:
1887:supporting line
1856:
1845:
1838:
1837:
1831:polygonal chain
1789:
1769:
1768:
1752:
1732:polynomial time
1721:polynomial time
1713:
1685:
1684:
1647:
1646:
1606:
1605:
1580:
1579:
1549:
1548:
1544:Ross Honsberger
1492:
1491:
1456:
1455:
1448:
1447:
1442:
1439:
1435:
1394:
1393:
1386:
1384:Specific shapes
1335:
1334:
1315:
1314:
1295:
1294:
1254:
1253:
1213:
1212:
1171:
1170:
1148:
1147:
1128:
1127:
1108:
1107:
1085:
1084:
1065:
1064:
1045:
1044:
1025:
1024:
1005:
1004:
985:
984:
977:Crofton formula
936:
935:
916:
915:
912:
879:convex polygons
854:
853:
821:
820:
798:
797:
775:
774:
771:
759:
731:
730:
707:
706:
676:
675:
644:
643:
613:
612:
593:
592:
561:
560:
541:
540:
505:
504:
485:
484:
465:
464:
445:
444:
425:
424:
405:
404:
382:
381:
362:
361:
358:
350:polynomial time
311:
310:
291:
290:
265:
264:
197:
196:
82:
81:
46:
45:
30:
23:
22:
15:
12:
11:
5:
3756:
3754:
3746:
3745:
3740:
3730:
3729:
3724:
3723:
3697:(9): 866–871,
3679:
3635:
3599:
3580:(4): 401–409,
3562:
3531:
3506:
3484:
3471:10211.3/198469
3435:
3396:
3378:(5): 275–276,
3357:
3352:
3348:
3344:
3341:
3324:
3298:(3): 193–198,
3280:
3274:
3248:
3217:
3195:
3156:
3138:(3): 456–478,
3120:
3094:(3): 206–207,
3073:
3039:
2992:
2972:
2941:
2927:
2902:
2864:
2830:
2770:
2718:
2665:
2624:
2588:(2): 315–334,
2549:
2523:Thomas, Doreen
2504:
2452:
2424:
2423:
2421:
2418:
2417:
2416:
2411:
2404:
2401:
2368:
2365:
2342:
2286:
2283:
2270:
2267:
2264:
2259:
2255:
2251:
2248:
2245:
2230:big O notation
2217:
2212:
2208:
2202:
2198:
2194:
2191:
2171:
2168:
2146:
2142:
2121:
2101:
2081:
2070:
2069:
2055:
2051:
2039:
2025:
2021:
2000:
1980:
1969:
1957:
1954:
1946:
1945:
1933:
1922:
1906:
1895:
1874:
1871:
1865:
1862:
1859:
1854:
1851:
1848:
1834:
1814:
1811:
1806:
1800:
1795:
1792:
1786:
1781:
1778:
1751:
1748:
1712:
1709:
1692:
1660:
1657:
1654:
1616:
1613:
1593:
1590:
1587:
1556:
1531:
1528:
1523:
1515:
1512:
1506:
1501:
1479:
1476:
1471:
1466:
1463:
1443:
1440:
1434:
1412:
1408:
1404:
1401:
1385:
1382:
1369:
1366:
1363:
1359:
1354:
1350:
1347:
1343:
1322:
1302:
1282:
1278:
1273:
1269:
1266:
1262:
1241:
1237:
1232:
1228:
1225:
1221:
1199:
1195:
1190:
1186:
1183:
1179:
1155:
1135:
1115:
1095:
1092:
1072:
1052:
1032:
1012:
992:
964:
960:
955:
951:
948:
944:
923:
911:
908:
861:
840:
836:
833:
829:
808:
805:
782:
770:
767:
758:
755:
751:convex polygon
738:
714:
683:
651:
620:
600:
568:
548:
512:
492:
472:
452:
432:
412:
389:
369:
357:
354:
338:convex polygon
318:
298:
278:
275:
272:
236:
233:
228:
220:
217:
211:
206:
178:opaque forests
162:beam detectors
150:lines of sight
121:
118:
113:
105:
102:
96:
91:
69:
66:
61:
56:
53:
28:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3755:
3744:
3741:
3739:
3736:
3735:
3733:
3720:
3716:
3712:
3708:
3704:
3700:
3696:
3692:
3691:
3683:
3680:
3676:
3672:
3668:
3664:
3660:
3656:
3652:
3648:
3647:
3639:
3636:
3632:
3628:
3624:
3620:
3616:
3612:
3611:
3603:
3600:
3595:
3591:
3587:
3583:
3579:
3575:
3574:
3566:
3563:
3559:
3555:
3551:
3547:
3546:
3541:
3535:
3532:
3528:
3521:
3517:
3510:
3507:
3502:
3495:
3488:
3485:
3481:
3477:
3472:
3467:
3463:
3459:
3455:
3451:
3450:
3442:
3440:
3436:
3432:
3428:
3424:
3420:
3416:
3412:
3411:
3403:
3401:
3397:
3393:
3389:
3385:
3381:
3377:
3373:
3372:
3350:
3346:
3339:
3328:
3325:
3321:
3317:
3313:
3309:
3305:
3301:
3297:
3293:
3292:
3284:
3281:
3277:
3271:
3267:
3263:
3259:
3252:
3249:
3245:
3241:
3237:
3233:
3232:
3227:
3221:
3218:
3214:
3210:
3206:
3199:
3196:
3193:
3189:
3184:
3180:
3176:
3173:(in French),
3172:
3171:
3163:
3161:
3157:
3153:
3149:
3145:
3141:
3137:
3133:
3132:
3124:
3121:
3117:
3113:
3109:
3105:
3101:
3097:
3093:
3089:
3088:
3083:
3077:
3074:
3070:
3066:
3062:
3058:
3054:
3050:
3043:
3040:
3036:
3032:
3028:
3024:
3020:
3016:
3012:
3008:
3007:
2990:
2979:
2977:
2973:
2969:
2965:
2961:
2957:
2956:
2948:
2946:
2942:
2938:
2934:
2930:
2924:
2920:
2916:
2912:
2906:
2903:
2899:
2895:
2890:
2885:
2881:
2877:
2876:
2868:
2865:
2861:
2857:
2853:
2849:
2845:
2841:
2834:
2831:
2827:
2823:
2819:
2815:
2811:
2807:
2803:
2799:
2798:
2793:
2792:Mycielski, J.
2789:
2783:
2781:
2779:
2777:
2775:
2771:
2767:
2763:
2759:
2755:
2751:
2747:
2746:
2738:
2734:
2727:
2725:
2723:
2719:
2715:
2711:
2707:
2703:
2699:
2695:
2690:
2685:
2681:
2674:
2672:
2670:
2666:
2662:
2658:
2654:
2650:
2646:
2642:
2638:
2631:
2629:
2625:
2621:
2617:
2613:
2609:
2605:
2601:
2596:
2591:
2587:
2583:
2582:
2577:
2570:
2568:
2566:
2564:
2562:
2560:
2558:
2556:
2554:
2550:
2546:
2542:
2537:
2532:
2528:
2524:
2517:
2515:
2513:
2511:
2509:
2505:
2501:
2497:
2493:
2489:
2486:(2): 99–103,
2485:
2481:
2480:
2475:
2471:
2465:
2463:
2461:
2459:
2457:
2453:
2448:
2444:
2440:
2434:
2432:
2430:
2426:
2419:
2415:
2412:
2410:
2407:
2406:
2402:
2400:
2398:
2394:
2390:
2385:
2382:
2378:
2374:
2366:
2364:
2362:
2358:
2340:
2330:
2329:distance sets
2325:
2323:
2319:
2315:
2311:
2307:
2303:
2296:
2291:
2284:
2282:
2265:
2262:
2257:
2253:
2249:
2243:
2233:
2231:
2210:
2206:
2200:
2196:
2189:
2169:
2166:
2144:
2140:
2119:
2099:
2079:
2053:
2049:
2040:
2023:
2019:
1998:
1978:
1970:
1967:
1963:
1962:
1961:
1955:
1953:
1951:
1931:
1923:
1920:
1904:
1896:
1893:
1888:
1872:
1869:
1863:
1860:
1857:
1852:
1849:
1846:
1835:
1832:
1828:
1812:
1809:
1804:
1798:
1793:
1790:
1784:
1779:
1776:
1766:
1765:
1764:
1762:
1758:
1750:Approximation
1749:
1747:
1745:
1741:
1737:
1733:
1728:
1726:
1722:
1718:
1710:
1708:
1706:
1690:
1682:
1678:
1677:Jan Mycielski
1674:
1658:
1655:
1652:
1644:
1640:
1639:
1634:
1614:
1611:
1591:
1588:
1585:
1576:
1572:
1570:
1554:
1545:
1529:
1526:
1521:
1513:
1510:
1504:
1499:
1477:
1474:
1469:
1464:
1461:
1453:
1446:
1432:
1430:
1426:
1410:
1406:
1402:
1399:
1391:
1383:
1381:
1367:
1364:
1361:
1357:
1348:
1320:
1300:
1280:
1276:
1267:
1239:
1235:
1226:
1197:
1193:
1184:
1167:
1153:
1133:
1113:
1093:
1090:
1070:
1050:
1030:
1010:
990:
982:
978:
962:
958:
949:
921:
909:
907:
905:
900:
896:
892:
888:
884:
880:
876:
859:
834:
806:
796:
780:
768:
766:
764:
756:
754:
752:
736:
728:
712:
705:
701:
697:
681:
673:
669:
668:connected set
665:
649:
640:
638:
634:
618:
598:
590:
589:opaque forest
586:
582:
581:line segments
566:
546:
538:
534:
533:beam detector
530:
526:
510:
490:
470:
450:
430:
410:
403:
387:
367:
355:
353:
351:
347:
343:
339:
335:
330:
316:
296:
276:
273:
270:
262:
258:
254:
250:
234:
231:
226:
218:
215:
209:
204:
194:
189:
187:
183:
179:
175:
174:line segments
171:
167:
166:opaque covers
163:
159:
155:
151:
147:
143:
139:
119:
116:
111:
103:
100:
94:
89:
67:
64:
59:
54:
51:
43:
39:
34:
27:
19:
3694:
3688:
3682:
3650:
3644:
3638:
3614:
3608:
3602:
3577:
3571:
3565:
3549:
3543:
3534:
3526:
3509:
3500:
3487:
3453:
3447:
3417:(1): 41–42,
3414:
3408:
3375:
3369:
3327:
3295:
3289:
3283:
3261:
3251:
3235:
3229:
3226:Stewart, Ian
3220:
3204:
3198:
3174:
3168:
3135:
3129:
3123:
3091:
3085:
3082:Stewart, Ian
3076:
3048:
3042:
3010:
3004:
2954:
2914:
2905:
2879:
2873:
2867:
2839:
2833:
2801:
2795:
2749:
2743:
2679:
2640:
2585:
2581:Algorithmica
2579:
2526:
2483:
2477:
2470:Bagemihl, F.
2446:
2442:
2386:
2370:
2326:
2314:Cantor space
2300:
2234:
2071:
1959:
1947:
1827:bounding box
1753:
1729:
1714:
1704:
1636:
1630:
1449:
1425:Fermat point
1387:
1168:
913:
899:single-curve
898:
890:
875:tangent line
772:
760:
699:
695:
641:
611:, including
588:
537:opaque cover
536:
532:
528:
524:
401:
359:
331:
309:and at most
190:
177:
165:
161:
157:
141:
135:
42:Steiner tree
26:
3617:: 461–469,
3552:: 199–201,
3177:(1): 1–14,
3013:: 535–537,
2882:: 130–138,
2733:Pach, János
2576:Pach, János
1966:convex hull
1757:linear-time
1673:Vance Faber
1643:Ian Stewart
1633:unit circle
1452:unit square
910:Lower bound
904:upper bound
769:Upper bound
672:convex hull
356:Definitions
346:linear time
257:unit circle
193:unit square
38:unit square
3743:Visibility
3732:Categories
3238:(2): 125,
3192:1910.00615
2645:Birkhäuser
2420:References
1763:than two:
1711:Algorithms
1641:column by
763:convex set
704:convex set
664:convex set
525:opaque set
360:Every set
334:algorithms
249:convex set
142:opaque set
3675:122556952
3653:: 67–82,
3213:459.52005
2991:α
2788:Faber, V.
2752:: 13–22,
2714:207211457
2689:1311.3323
2595:1005.2218
2536:1210.8139
2389:geodesics
2359:) form a
2310:limit set
2263:
1964:Find the
1870:≈
1858:π
1847:π
1810:≈
1805:π
1659:π
1612:≈
1592:π
1527:≈
1475:≈
1403:π
1368:δ
1346:∂
1321:δ
1265:∂
1224:∂
1182:∂
947:∂
891:connected
832:∂
804:∂
297:π
277:π
261:connected
253:perimeter
232:≈
188:in 1959.
152:across a
117:≈
65:≈
3320:37582183
3244:24989406
3116:24981805
3053:Springer
2735:(2019),
2620:13884553
2472:(1959),
2403:See also
1956:Coverage
1390:triangle
883:vertices
795:boundary
402:coverage
158:barriers
3719:1191707
3711:2324127
3667:2390069
3631:0247601
3594:2315418
3558:0080287
3480:3376125
3431:1134007
3392:0981078
3312:0882227
3183:0559167
3152:0675417
3096:Bibcode
3069:1804684
3035:0164898
3027:2312596
2937:0490615
2898:3544574
2826:0867106
2818:2322935
2766:3945133
2706:3382335
2661:1457290
2612:3183418
2541:Bibcode
2500:0105657
2449:: 11–16
2397:infimum
2367:History
2295:fractal
1873:1.5835.
1813:1.5868.
1555:2.00002
727:infimum
529:barrier
503:, then
154:polygon
3717:
3709:
3673:
3665:
3629:
3592:
3556:
3478:
3429:
3390:
3318:
3310:
3272:
3242:
3211:
3181:
3150:
3114:
3067:
3033:
3025:
2935:
2925:
2896:
2858:
2824:
2816:
2764:
2712:
2704:
2659:
2618:
2610:
2498:
1932:1.7168
1905:1.5716
1723:using
1691:4.7998
1615:4.7998
1450:For a
1388:For a
881:, all
757:Bounds
698:or an
585:forest
400:, its
317:4.7998
170:forest
3707:JSTOR
3671:S2CID
3590:JSTOR
3523:(PDF)
3497:(PDF)
3316:S2CID
3240:JSTOR
3188:arXiv
3112:JSTOR
3023:JSTOR
2856:JSTOR
2814:JSTOR
2740:(PDF)
2710:S2CID
2684:arXiv
2616:S2CID
2590:arXiv
2531:arXiv
2391:on a
2132:sets
1530:2.639
1478:2.732
662:is a
535:, or
235:2.639
146:plane
140:, an
120:2.639
68:2.732
3270:ISBN
2923:ISBN
2327:The
1675:and
539:for
3699:doi
3655:doi
3651:133
3619:doi
3582:doi
3466:hdl
3458:doi
3419:doi
3380:doi
3300:doi
3236:274
3209:Zbl
3140:doi
3104:doi
3092:273
3057:doi
3015:doi
3003:",
2964:doi
2884:doi
2880:213
2848:doi
2806:doi
2754:doi
2694:doi
2649:doi
2600:doi
2488:doi
2254:log
773:If
344:in
172:of
136:In
3734::
3715:MR
3713:,
3705:,
3695:99
3693:,
3669:,
3663:MR
3661:,
3649:,
3627:MR
3625:,
3588:,
3578:73
3576:,
3554:MR
3550:47
3548:,
3525:,
3499:,
3476:MR
3474:,
3464:,
3454:29
3452:,
3438:^
3427:MR
3425:,
3415:40
3413:,
3399:^
3388:MR
3386:,
3376:29
3374:,
3314:,
3308:MR
3306:,
3296:24
3294:,
3260:,
3234:,
3179:MR
3175:35
3159:^
3148:MR
3146:,
3136:45
3110:,
3102:,
3090:,
3065:MR
3063:,
3031:MR
3029:,
3021:,
3011:71
3009:,
2975:^
2944:^
2933:MR
2931:,
2894:MR
2892:,
2878:,
2854:,
2842:,
2822:MR
2820:,
2812:,
2802:93
2800:,
2790:;
2773:^
2762:MR
2760:,
2750:80
2748:,
2742:,
2721:^
2708:,
2702:MR
2700:,
2692:,
2668:^
2657:MR
2655:,
2627:^
2614:,
2608:MR
2606:,
2598:,
2586:69
2584:,
2552:^
2539:,
2529:,
2507:^
2496:MR
2494:,
2482:,
2476:,
2455:^
2447:27
2428:^
2363:.
2232:.
1952:.
1707:.
1431:.
1380:.
531:,
527:,
423:.
352:.
329:.
164:,
160:,
3701::
3657::
3621::
3615:1
3584::
3468::
3460::
3421::
3382::
3356:)
3351:3
3347:n
3343:(
3340:O
3302::
3190::
3142::
3106::
3098::
3059::
3017::
2966::
2886::
2850::
2808::
2756::
2696::
2686::
2651::
2602::
2592::
2543::
2533::
2490::
2484:6
2341:2
2269:)
2266:n
2258:2
2250:n
2247:(
2244:O
2216:)
2211:2
2207:n
2201:2
2197:m
2193:(
2190:O
2170:m
2167:2
2145:p
2141:C
2120:n
2100:m
2080:n
2054:p
2050:C
2038:.
2024:p
2020:C
1999:p
1979:p
1864:2
1861:+
1853:5
1850:+
1799:2
1794:+
1791:2
1785:+
1780:2
1777:1
1656:+
1653:2
1627:.
1589:+
1586:2
1522:6
1514:2
1511:1
1505:+
1500:2
1470:3
1465:+
1462:1
1438::
1411:3
1407:/
1400:2
1365:+
1362:2
1358:/
1353:|
1349:K
1342:|
1301:K
1281:2
1277:/
1272:|
1268:K
1261:|
1240:2
1236:/
1231:|
1227:K
1220:|
1198:2
1194:/
1189:|
1185:K
1178:|
1154:K
1134:p
1114:K
1094:p
1091:2
1071:p
1051:K
1031:K
1011:K
991:K
963:2
959:/
954:|
950:K
943:|
922:K
860:K
839:|
835:K
828:|
807:K
781:K
737:P
713:P
682:K
650:K
619:K
599:K
567:S
547:K
511:S
491:S
471:K
451:S
431:C
411:C
388:S
368:S
274:+
271:2
227:6
219:2
216:1
210:+
205:2
132:.
112:6
104:2
101:1
95:+
90:2
60:3
55:+
52:1
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
