Opaque set (original) (raw)
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.
| Property | Value |
|---|---|
| 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) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Unit_Square_Opaque_Forest_Solutions.svg?width=300 |
| dbo:wikiPageID | 41162601 (xsd:integer) |
| dbo:wikiPageLength | 31581 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1120082125 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bellman's_lost_in_a_forest_problem dbr:Probability_distribution dbr:Ross_Honsberger dbr:Scientific_American dbr:Algorithm dbr:Approximation_algorithm dbr:Unit_circle dbr:Upper_bound dbr:Vance_Faber dbr:Jan_Mycielski dbr:Line_segment dbr:Limit_set dbr:Convex_set dbr:Crofton_formula dbr:Menachem_Magidor dbr:Equilateral_triangle dbr:Geodesic dbr:Boundary_(topology) dbr:Continuum_hypothesis dbr:Convex_hull dbr:Convex_polygon dbc:Discrete_geometry dbr:Linear_time dbr:Sightline dbr:Stefan_Mazurkiewicz dbr:Steiner_tree_problem dbr:Perimeter dbr:Plane_(geometry) dbr:Polygon dbr:Travelling_salesman_problem dbr:Distance_set dbr:Hausdorff_dimension dbr:Hausdorff_measure dbc:Visibility dbr:Dynamic_programming dbr:Euclid's_orchard dbr:Null_set dbr:Discrete_geometry dbr:Riemannian_manifold dbr:Hiranmay_Sen_Gupta dbr:Big_O_notation dbr:Polygon_triangulation dbr:Triangle dbr:Rectifiable_set dbr:Polynomial-time_approximation_scheme dbr:Fermat_point dbr:Frederick_Bagemihl dbr:Polynomial_time dbr:Approximation_ratio dbr:Ian_Stewart_(mathematician) dbr:Cantor_space dbr:Rotating_calipers dbr:Infimum dbr:Unit_square dbr:Vertex_(geometry) dbr:Supporting_line dbr:Forest_(graph_theory) dbr:Polygonal_chain dbr:Sum_of_radicals dbr:Tangent_line dbr:Connected_set dbr:Bounding_box dbr:File:Circular_beam_detectors.svg dbr:File:Fractal_opaque_set.svg dbr:File:Unit_Square_Opaque_Forest_Solutions.svg |
| dbp:wikiPageUsesTemplate | dbt:Good_article dbt:Harvtxt dbt:R dbt:Reflist dbt:Short_description dbt:Unsolved |
| dcterms:subject | dbc:Discrete_geometry dbc:Visibility |
| 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) |
| rdfs:label | Opaque set (en) Задача про густий ліс (uk) |
| owl:sameAs | wikidata:Opaque set dbpedia-sr:Opaque set dbpedia-uk:Opaque set https://global.dbpedia.org/id/emDA |
| prov:wasDerivedFrom | wikipedia-en:Opaque_set?oldid=1120082125&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Circular_beam_detectors.svg wiki-commons:Special:FilePath/Fractal_opaque_set.svg wiki-commons:Special:FilePath/Unit_Square_Opaque_Forest_Solutions.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Opaque_set |
| is dbo:wikiPageRedirects of | dbr:Approximation_algorithms_for_the_opaque_forest_problem dbr:Opaque_forest_problem |
| is dbo:wikiPageWikiLink of | dbr:Approximation_algorithms_for_the_opaque_forest_problem dbr:Opaque_forest_problem dbr:List_of_unsolved_problems_in_mathematics |
| is foaf:primaryTopic of | wikipedia-en:Opaque_set |
