LIPIcs.FUN.2016.17.pdf
- Filesize: 401 kB
- 7 pages
Document
Counting Circles Without Computing Them
Author
-
Part of:
Volume:
8th International Conference on Fun with Algorithms (FUN 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-02
Cite As Get 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.
Subject Classification
Keywords
- lines arrangement
- triangle
- circumcircle
- inscribed angle theorem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- ACM-ICPC International Collegiate Programming Contest. URL: https://icpc.baylor.edu.
- Problem 603D-36: Ruminations on Ruminants. Codeforces, Contest 342, Division 1, 2015, Dec 1. URL: http://codeforces.com/contest/603/problem/D.
- 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.
- 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.
-
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.
- R. Fleischer. Problem 603D-36: Submission 14741117. Codeforces, Contest 342, Division 1, 2015, Dec 10. URL: http://codeforces.com/contest/603/submission/14741117.
- R. Fleischer. Problem 603D-36: Submission 16228941. Codeforces, Contest 342, Division 1, 2016, Jan 20. URL: http://codeforces.com/contest/603/submission/16228941.
- R. Fleischer. Problem 603D-36: Submission 16231449. Codeforces, Contest 342, Division 1, 2016, Jan 20. URL: http://codeforces.com/contest/603/submission/16231449.
-
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.
- M. Mirzayanov. Codeforces: The only programming contests web 2.0 platform, 2010-2016. URL: http://codeforces.com.
- Z. Shi. Problem 603D-36: Submission 15094164. Codeforces, Contest 342, Division 1, 2015, Dec 30. URL: http://codeforces.com/contest/603/submission/15094164.