A note on the 1-maximal elements problem

Abstract

Consider a set of S points in the plane. A point p in S is said to be k-maximal if exactly k elements in S dominate p. We propose a very simple, cost-optimal, EREW algorithm to solve the 1-maximal elements problem in the plane.

Keywords:

• Parallel algorithms
• optimal algorithms
• domination
• computational geometry
• maximal elements

C.R Categories:

• B.7.1
• C.1.2
• F.2.2
• G.2.2