| dbo:abstract
|
- 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 . 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 . Without the assumption of connectivity, the shortest opaque set for the circle has length at least and at most . 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. (en)
- В обчислювальній геометрії, проблема густого лісу може бути сформульована таким чином: «Для опуклого багатокутника С в площині, визначити мінімальний ліс Т замкнених, обмежених відрізків, таких, що кожна лінія, яка проходить через C, також перетинає Т». Т називається густим лісом, або бар'єром для C. Відповідно C називається охопленням T. Задача в тому, щоб серед усіх лісів, які охоплюють С (є бар'єром для C), знайти ліс з найменшою довжиною. У випадку коли Т розташований тільки у внутрішній або тільки у зовнішній частині C, тоді бар'єр називається, відповідно, внутрішнім або зовнішнім. В інших випадках, вважається, що на бар'єр не накладається жодних обмежень. (uk)
|
| rdfs:comment
|
- 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. (en)
- В обчислювальній геометрії, проблема густого лісу може бути сформульована таким чином: «Для опуклого багатокутника С в площині, визначити мінімальний ліс Т замкнених, обмежених відрізків, таких, що кожна лінія, яка проходить через C, також перетинає Т». Т називається густим лісом, або бар'єром для C. Відповідно C називається охопленням T. Задача в тому, щоб серед усіх лісів, які охоплюють С (є бар'єром для C), знайти ліс з найменшою довжиною. (uk)
|
