On the maximum triangle problem

Document Type : Article

Authors

1 Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, Netherlands

2 Department of Computer Engineering, Sharif University of Technology, Tehran, Iran

Abstract

Given a set $P$ of $n$ points in the plane, the maximum triangle problem asks for finding a triangle with three vertices in $P$ that encloses the maximum number of points from $P$. While the problem is easily solvable in $O(n^3)$ time, it has been open whether a subcubic solution is possible. In this paper, we show that the problem can be solved in $o(n^3)$ time, using a reduction to min-plus matrix multiplication. We also provide some improved approximation algorithms for the problem, including a 4-approximation algorithm running in $O(n \log n \log h)$ time, and a 3-approximation algorithm with $O(nh \log n + nh^2)$ runtime, where $h$ is the size of the convex hull of $P$.

Keywords

Main Subjects

References

References:
1. Eppstein, D., Overmars, M., Rote, G., et al. "Finding minimum area k-gons", Discrete Comput. Geom., 7(1), pp. 45-58 (1992). DOI: 10.1007/BF02187823.
2. Douieb, K., Eastman, M., Maheshwari, A., et al. "Approximation algorithms for a triangle enclosure problem", In Proc. 23rd Canad. Conf. Computat. Geom., pp. 105-110 (2011).
3. Boyce, J.E., Dobkin, D.P., Drysdale III, R.L., et al. "Finding extremal poly-gons", SIAM J. Comput., 14(1), pp. 134-147 (1985). DOI: 10.1137/0214011.
4. Aggarwal, A., Klawe, M.M., Moran, S., et al. "Geometric applications of a matrix-searching algorithm", Algorithmica, 2, pp. 195-208 (1987). DOI: 10.1007/BF01840359.
5. Al Hasan, M. and Dave, V.S. "Triangle counting in large networks: a review", Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 8(2), e1226 (2018). DOI: 10.1002/widm.1226.
6. Ribeiro, P., Paredes, P., Silva, M.E., et al. "A survey on subgraph count-ing: concepts, algorithms, and applications to network motifs and graphlets", ACM Computing Surveys, 54(2), pp. 1-36 (2021). DOI: 10.1145/3433652.
7. Duan, R., Wu, H., and Zhou, R. "Faster matrix multiplication via asymmetric hashing", In Proc. 64th Annu. IEEE Sympos. Found. Comput. Sci., pp. 2129- 2138 (2023). DOI: 10.1109/FOCS57990.2023.00130.
8. Williams, V.V., Xu, Y., Xu, Z., et al. "New bounds for matrix multiplica-tion: from alpha to omega", In Proc. 35th ACM-SIAM Sympos. Discrete Algorithms, pp. 3792-3835 (2024). DOI: 10.1137/1.9781611977912.134.
9. Jayaram, R. and Kallaugher, J. "An optimal algorithm for triangle counting in the stream", In Proc. Internat. Workshop Approx. Algorithms, pp. 11:1-11:11 (2021). DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.11.
10. Sharafeldeen, A., Alrahmawy, M., and Elmougy, S. "Graph partitioning MapReduce-based algorithms for counting triangles in large-scale graphs", Scientific Reports, 13(1), p. 166 (2023). DOI: 10.1038/s41598-022-25243-w.
11. Dhulipala, L., Liu, Q.C., Shun, J., et al. "Parallel batch-dynamic k-clique counting", In Proc. Sympos. Algorithmic Principles of Computer Systems, pp. 129- 143 (2021). DOI: 10.1137/1.9781611976489.
12. Ding, X., Sheng, S., Zhou, H., et al. "Differentially private triangle counting in large graphs", IEEE Trans. Knowledge and Data Engineering, 34(11), pp. 5278- 5292 (2022). DOI: 10.1109/TKDE.2021.3052827.
13. Chan, T.M. "Finding triangles and other small subgraphs in geometric inter-section graphs", In Proc. 34th ACM-SIAM Sympos. Discrete Algorithms, pp. 1777-1805 (2023). DOI: 10.1137/1.9781611977554.ch68.
14. Dumitrescu, A. and Lingas, A. "Finding small complete subgraphs eciently", In Proc. 34th Internat. Workshop Combinatorial Algorithms, pp. 185-196 (2023). DOI: 10.1007/978-3-031-34347-6 16.
15. Dalirrooyfard, M., Vuong, T.D., and Williams, V.V. "Graph pattern detection: Hardness for all induced patterns and faster noninduced cycles", SIAM J. Comput., 50(5), pp. 1627-1662 (2021). DOI: 10.1137/20M1335054.
16. Williams, V.V. and Williams, R. "Subcubic equivalences between path, matrix, and triangle problems", J. ACM, 65(5), p. 27 (2018). DOI: 10.1145/3186893.
17. Chan, T.M. "More algorithms for all-pairs shortest paths in weighted graphs", SIAM J. Comput., 39(5), pp. 2075-2089 (2010). DOI: 10.1137/08071990X.
18. Fredman, M.L. "New bounds on the complexity of the shortest path problem", SIAM J. Comput., 5(1), pp. 83-89 (1976).
DOI: 10.1137/0205006.
19. Williams, R.R. "Faster all-pairs shortest paths via circuit complexity", SIAM Journal on Computing, 47(5), pp. 1965-1985 (2018). DOI: 10.1137/15M1024524.
20. Chan, T.M. and Williams, R. "Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov-Smolensky", In Proc. 27th ACM-SIAM Sympos. Discrete Algorithms, pp. 1246-1255 (2016). DOI: 10.1137/1.9781611974331.ch87.
21. Williams, V.V. "On some fine-grained questions in algorithms and complexity", In Proc. Internat. Congress Math., pp. 3447-3487 (2018). DOI: 10.1142/9789813272880 0188.
Scientia Iranica
Volume 31, Issue 14
Transactions on Computer Science & Engineering and Electrical Engineering (D)
July and August 2024
Pages 1143-1148

Files

Share

How to cite

Statistics