We study the problem of computing the minimum area triangle that circumscribes a given n-sided convex polygon touching edge-to-edge. In other words, we compute the minimum area triangle that is the intersection of 3 half-planes out of n half-planes defined by a given convex polygon. Previously, } O(n  \log n) time algorithms were known which are based on the technique for computing the minimum weight k-link path given in [A. Aggarwal et. al. DCG94; B. Schieber. SODA95}. By applying the new technique proposed in Jin's recent work for the dual problem of computing the maximum area triangle inside a convex polygon, we solve the problem at hand in O(n) time, thus justify Jin's claim that his technique may find applications in other polygon inclusion problems. Our algorithm actually computes all the local minimal area circumscribing triangles touching edge-to-edge.
We study the problem of computing the minimum area triangle that circumscribes a given n-sided convex polygon touching edge-to-edge. In other words, we compute the minimum area triangle that is the intersection of 3 half-planes out of n half-planes defined by a given convex polygon. Building on the Rotate-and-Kill technique Arxiv:1707.04071}, we propose an algorithm that solves the problem in O(n ) time, improving the best-known O(n \log n) time algorithms given in [A. Aggarwal et. al. DCG94; B. Schieber. SODA95}. Our algorithm computes all the locally minimal area circumscribing triangles touching edge-to-edge.
R
Previously,
Building on the Rotate-and-Kill technique
A
Arxiv:1707.04071
A
, we propose an algorithm that solves the problem in
A
) time, improving the best-known O(n
D
were known which are based on the technique for computing the minimum weight k-link path
R
By applying the new technique proposed in Jin's recent work for the dual problem of computing the maximum area triangle inside a convex polygon, we solve the problem at hand in O(n) time, thus justify Jin's claim that his technique may find applications in other polygon inclusion problems. Our algorithm actually
Our algorithm
R
local
locally