On the Maximum Triangle Problem

Jabal Ameli, Afrouz; Zarrabi-Zadeh, Hamid

doi:10.24200/sci.2024.64287.8852

On the Maximum Triangle Problem

Document Type : Article

Authors

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

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

10.24200/sci.2024.64287.8852

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