The Opaque Square

DOI10.1145/2582112.2582113zbMATH Open1396.52002arXiv1311.3323OpenAlexW2082617679MaRDI QIDQ4635579FDOQ4635579

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)

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.

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

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

Cited In (5)

• A lower bound on opaque sets
• Improving the lower bound on opaque sets for equilateral triangle
• Title not available (Why is that?)
• Computing Opaque Interior Barriers à la Shermer
• The diaphanous wedge

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)