In this paper, we consider 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 \mbox{%DIFAUXCMD kgon94,kgon95soda  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 polygonal 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. 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.
R
In this paper, we consider
We study
R
\mbox{%DIFAUXCMD kgon94,kgon95soda
A. Aggarwal et. al. DCG94; B. Schieber. SODA95
A
.
R
polygonal
polygon