Counting Circles Without Computing Them

Author Rudolf Fleischer



PDF
Thumbnail PDF

File

LIPIcs.FUN.2016.17.pdf
  • Filesize: 401 kB
  • 7 pages

Document Identifiers

Author Details

Rudolf Fleischer

Cite AsGet BibTex

Rudolf Fleischer. Counting Circles Without Computing Them. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 17:1-17:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FUN.2016.17

Abstract

In this paper we engineer a fast algorithm to count the number of triangles defined by three lines out of a set of n lines whose circumcircle contains the origin. The trick is not to compute any triangles or circles.
Keywords
  • lines arrangement
  • triangle
  • circumcircle
  • inscribed angle theorem

Metrics

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

References

  1. ACM-ICPC International Collegiate Programming Contest. URL: https://icpc.baylor.edu.
  2. Problem 603D-36: Ruminations on Ruminants. Codeforces, Contest 342, Division 1, 2015, Dec 1. URL: http://codeforces.com/contest/603/problem/D.
  3. Wikipedia contributors. Inscribed angle, Date retrieved: 20 February 2016 15:40 UTC. Permanent link: URL: https://en.wikipedia.org/w/index.php?title=Inscribed_angle&oldid=699778165.
  4. Wikipedia contributors. Arrangement of lines, Date retrieved: 29 February 2016 15:24 UTC. Permanent link: URL: https://en.wikipedia.org/w/index.php?title=Arrangement_of_lines&oldid=702141041.
  5. R. Fleischer. FUN with implementing algorithms. In E. Lodi, L. Pagli, and N. Santoro, editors, Proceedings of the 1998 International Conference FUN with Algorithms (FUN'98), pages 88-98. Carleton Scientific, Proceedings in Informatics 4, 1999. Google Scholar
  6. R. Fleischer. Problem 603D-36: Submission 14741117. Codeforces, Contest 342, Division 1, 2015, Dec 10. URL: http://codeforces.com/contest/603/submission/14741117.
  7. R. Fleischer. Problem 603D-36: Submission 16228941. Codeforces, Contest 342, Division 1, 2016, Jan 20. URL: http://codeforces.com/contest/603/submission/16228941.
  8. R. Fleischer. Problem 603D-36: Submission 16231449. Codeforces, Contest 342, Division 1, 2016, Jan 20. URL: http://codeforces.com/contest/603/submission/16231449.
  9. R. Fleischer and Y. Wang. On the camera placement problem. In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC'09). Springer Lecture Notes in Computer Science 5878, pages 255-264, 2009. Google Scholar
  10. M. Mirzayanov. Codeforces: The only programming contests web 2.0 platform, 2010-2016. URL: http://codeforces.com.
  11. Z. Shi. Problem 603D-36: Submission 15094164. Codeforces, Contest 342, Division 1, 2015, Dec 30. URL: http://codeforces.com/contest/603/submission/15094164.
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