Document Open Access Logo

Ruler of the Plane - Games of Geometry (Multimedia Contribution)

Authors Sander Beekhuis, Kevin Buchin, Thom Castermans, Thom Hurks, Willem Sonke

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.63.pdf
  • Filesize: 2.27 MB
  • 5 pages

Document Identifiers

Author Details

Sander Beekhuis
Kevin Buchin
Thom Castermans
Thom Hurks
Willem Sonke

Cite As Get BibTex

Sander Beekhuis, Kevin Buchin, Thom Castermans, Thom Hurks, and Willem Sonke. Ruler of the Plane - Games of Geometry (Multimedia Contribution). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 63:1-63:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.63

Abstract

Ruler of the Plane is a set of games illustrating concepts from combinatorial and computational geometry. The games are based on the art gallery problem, ham-sandwich cuts, the Voronoi game, and geometric network connectivity problems like the Euclidean minimum spanning tree and traveling salesperson problem.

Subject Classification

Keywords
  • art gallery problem
  • ham-sandwich cuts
  • Voronoi game
  • traveling sales-person problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin, and Rene Van Oostrum. Competitive facility location: the Voronoi game. Theoretical Computer Science, 310(1-3):457-467, 2004. Google Scholar
  2. Martin Aigner and Günter M. Ziegler. Proofs from THE BOOK. Springer, 4th edition, 2009. Google Scholar
  3. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. Int. J. Comput. Geom. Appl., 5:75-91, 1995. Google Scholar
  4. Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete &Computational Geometry, 9(1):81-100, 1993. Google Scholar
  5. Yoav Amit, Joseph S. B. Mitchell, and Eli Packer. Locating guards for visibility coverage of polygons. Int. J. Comput. Geom. Appl., 20:601-630, 2010. Google Scholar
  6. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer, 3rd edition, 2008. Google Scholar
  7. Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, 1976. Google Scholar
  8. Der-Tsai Lee and Arthur K. Lin. Computational complexity of art gallery problems. IEEE Transactions on Information Theory, 32(2):276-282, 1986. Google Scholar
  9. Chi-Yuan Lo, Jiří Matoušek, and William Steiger. Algorithms for ham-sandwich cuts. Discrete &Computational Geometry, 11(4):433-452, 1994. Google Scholar
  10. Matthias Müller-Hannemann and Stefan Schirra, editors. Algorithm engineering: bridging the gap between algorithm theory and practice, volume 5971 of LNCS. Springer, 2010. Google Scholar
  11. Giri Narasimhan and Michiel Smid. Geometric Spanner Networks. Cambridge University Press, New York, NY, USA, 2007. Google Scholar
  12. Jonathan Richard Shewchuk. Lecture notes on geometric robustness, 2013. Google Scholar
  13. Kevin Weiler and Peter Atherton. Hidden surface removal using polygon area sorting. ACM SIGGRAPH computer graphics, 11(2):214-222, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact