The opaque square

DOI10.1145/2582112.2582113MaRDI QIDQ4635579zbMATH OpenOpenAlexFDO

Authors Adrian Dumitrescu, Minghui Jiang

Publication date 23 April 2018

Published in Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.3323

zbMATH Keywords

measure of a set of linesopaque square problem

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: The problem of finding small sets that block every line passing through a unit square was first considered by Mazurkiewicz in 1916. We call such a set {em opaque} or a {em barrier} for the square. The shortest known barrier has length $sqrt2+fracsqrt62=2.6389ldots$. The current best lower bound for the length of a (not necessarily connected) barrier is $2$, as established by Jones about 50 years ago. No better lower bound is known even if the barrier is restricted to lie in the square or in its close vicinity. Under a suitable locality assumption, we replace this lower bound by $2+10^{-12}$, which represents the first, albeit small, step in a long time toward finding the length of the shortest barrier. A sharper bound is obtained for interior barriers: the length of any interior barrier for the unit square is at least $2+10^{-5}$. Two of the key elements in our proofs are: (i) formulas established by Sylvester for the measure of all lines that meet two disjoint planar convex bodies, and (ii) a procedure for detecting lines that are witness to the invalidity of a short bogus barrier for the square.

Recommendations

• Opaque sets
• Opaque sets
• A lower bound on opaque sets
• A lower bound on opaque sets
• Improving the lower bound on opaque sets for equilateral triangle

Cited in

(11)

• A lower bound on opaque sets
• Computing opaque interior barriers à la Shermer
• Opaque sets
• A lower bound on opaque sets
• Improving the lower bound on opaque sets for equilateral triangle
• The diaphanous wedge
• Opaque sets
• The Opaque Cube Problem
• scientific article; zbMATH DE number 5268909 (Why is no real title available?)
• Computing Opaque Interior Barriers à la Shermer
• A stability version of the Jones opaque set inequality

This page was built for publication: The opaque square

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635579)