Before revision:  We also present a deterministic O(n\log n)-time algorithm for the case that the input points are in convex position  .
After revision:  We also present a deterministic O(n\log n)-time algorithm for the case that the input points are in convex position . Both results improve the previous best O(n\log n\log\log n) bound on the problems .