Quantcast

Lower bounds for maximal and convex layers problems

Research paper by Sanjiv Kapoor, Prakash Ramanan

Indexed on: 01 Jun '89Published on: 01 Jun '89Published in: Algorithmica



Abstract

In this paper we derive tight lower bounds for the maximal and convex layers problems in the plane. Our lower bound proofs for the maxima problem and convex hull problem are simpler than those previously known. We also obtain an Ω(nlog n) lower bound for the maximal depth problem, and the convex depth problem, when the points are given in sorted order of their x-coordinates.