About: Opaque set

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Opaque set Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FOpaque_set&graph=http%3A%2F%2Fdbpedia.org&graph=http%3A%2F%2Fdbpedia.org

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.

Attributes	Values
rdfs:label	Opaque set (en) Задача про густий ліс (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)
foaf:depiction
dcterms:subject	Discrete geometry Visibility
Wikipage page ID	41162601 (xsd:integer)
Wikipage revision ID	1120082125 (xsd:integer)
Link from a Wikipage to another Wikipage	Bellman's lost in a forest problem Probability distribution Ross Honsberger Scientific American Algorithm Approximation algorithm Unit circle Upper bound Vance Faber Jan Mycielski Line segment Limit set Convex set Crofton formula Menachem Magidor Equilateral triangle Geodesic Boundary (topology) Continuum hypothesis Convex hull Convex polygon Discrete geometry Linear time Sightline Stefan Mazurkiewicz Steiner tree problem Perimeter Plane (geometry) Polygon Travelling salesman problem Distance set Hausdorff dimension Hausdorff measure Visibility Dynamic programming Euclid's orchard Null set Discrete geometry Riemannian manifold Hiranmay Sen Gupta Big O notation Polygon triangulation Triangle Rectifiable set Polynomial-time approximation scheme Fermat point Frederick Bagemihl Polynomial time Approximation ratio Ian Stewart (mathematician) Cantor space Rotating calipers Infimum Unit square Vertex (geometry) Supporting line Forest (graph theory) Polygonal chain Sum of radicals Tangent line Connected set Bounding box
sameAs	Opaque set Opaque set Opaque set Opaque set
dbp:wikiPageUsesTemplate	dbt:Good_article dbt:Harvtxt dbt:R dbt:Reflist dbt:Short_description dbt:Unsolved
thumbnail	wiki-commons:Special:FilePath/Unit_Square_Opaque_Forest_Solutions.svg?width=300
has 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)
prov:wasDerivedFrom	wikipedia-en:Opaque_set?oldid=1120082125&ns=0
page length (characters) of wiki page	31581 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Opaque_set
is Link from a Wikipage to another Wikipage of	Approximation algorithms for the opaque forest problem Opaque forest problem List of unsolved problems in mathematics
is Wikipage redirect of	Approximation algorithms for the opaque forest problem Opaque forest problem
is foaf:primaryTopic of	wikipedia-en:Opaque_set

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 56 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software