Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/1542362.1542394acmconferencesArticle/Chapter ViewAbstractPublication PagessocgConference Proceedingsconference-collections
research-article

Candle in the woods: asymptotic bounds on minimum blocking sets

Published: 08 June 2009 Publication History

Abstract

We consider the problem of determining the minimum number Nd of unit disks that is required to block all rays emanating from a point P in the two-dimensional space, where each disk has at least a distance d to point P and to any other disk. We study the asymptotic behavior of Nd, as d tends to infinity. By deriving upper bounds and lower bounds, we prove that pi2/16 ≤ lim_{d -> infinity} N_d/d2 ≤ 18/pi2, where the upper bound is based on establishing an interesting link between unit disks positioned on a regular triangular grid and Farey sequences from number theory. By positioning point P as well as the centers of the disks on the grid points of such a triangular grid, we create hexagonal rings of disks around P. We prove that we need exactly d-1 of these hexagons to block all rays emanating from P.

References

[1]
J.Conway and R.Guy. The Book of Numbers. Springer, 1995.
[2]
L.Dickson. History of the Theory of Numbers, Volume I: Divisibility and Primality. Dover Publications, 2005.
[3]
R.Fulek, A.F. Holmsen and J. Pach. Intersecting convex sets by rays. In SCG '08: Proceedings of the twenty-fourth annual symposium on Computational geometry, pages 385--391, New York, NY, USA, 2008. ACM.
[4]
J.Goodman and J.O'Rourke. Handbook of discrete and computational geometry. Chapman & Hall/CRC, 2nd edition, 2004.
[5]
R.L. Graham, D.E. Knuth and O.Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1994.
[6]
G.H. Hardy and E.M. Wright. An Introduction to the Theory of Numbers. Oxford University Press, London, UK, 1979.Fifth Edition.
[7]
G.Hollemans, T.Bergman, V.Buil, K.van Gelder, M.Groten, J.Hoonhout, T.Lashina, E.van Loenen and S.van de Wijdeven. Entertaible: Multi-user multi-object concurrent input. Adjunct Proceedings of UIST, 6:55--56, 2006.
[8]
N.Jovanovic, J.Korst and A.J.E.M. Janssen. Minimum blocking sets of circles for a set of lines in the plane. Proceedings of the 20th Canadian Conference on Computational Geometry, pages 91--94, 2008.
[9]
H.Melissen. Packing and Covering with Circles. PhD thesis, Utrecht University, Utrecht, The Netherlands, 1997.
[10]
J.Pach and P.Agarwal. Combinatorial Geometry. Wiley-Interscience, New York, 1995.

Cited By

View all

Index Terms

  1. Candle in the woods: asymptotic bounds on minimum blocking sets

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry
    June 2009
    426 pages
    ISBN:9781605585017
    DOI:10.1145/1542362
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 08 June 2009

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. asymptotic bounds
    2. blocking set
    3. farey sequences

    Qualifiers

    • Research-article

    Conference

    SoCG '09

    Acceptance Rates

    Overall Acceptance Rate 625 of 1,685 submissions, 37%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 19 Sep 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2019)The Forest Hiding ProblemDiscrete & Computational Geometry10.5555/3116271.311649445:3(529-552)Online publication date: 1-Jan-2019
    • (2012)ZeroTouchProceedings of the SIGCHI Conference on Human Factors in Computing Systems10.1145/2207676.2208368(2165-2174)Online publication date: 5-May-2012
    • (2010)The forest hiding problemProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873728(1566-1579)Online publication date: 17-Jan-2010
    • (2010)The Forest Hiding ProblemDiscrete & Computational Geometry10.1007/s00454-010-9261-445:3(529-552)Online publication date: 8-May-2010
    • (2009)Object Detection in FlatlandProceedings of the 2009 Third International Conference on Advanced Engineering Computing and Applications in Sciences10.1109/ADVCOMP.2009.21(95-100)Online publication date: 11-Oct-2009

    View Options

    Get Access

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media