Maxima of a point set - Wikiwand

Problem. Let be a set of n points in the two-dimensional Euclidean plane. A point dominates another point if (that is, if it is up and to the right). A point is maximal if it is not dominated by any other point.


# A[(int, int)] is the structure of the array
function FindMaximal()
	max_y = -Infinity
	# Sort the points in decreasing order by x-coordinate
	max_y = A[0]
	result = [A[0]]
	# traverse in reverse x direction (right to left)
	for p in A
		# if y is bigger than anything seen before it's maximal
		if p.y > max_y then
			max_y = p.y
	return result
  • ReverseMergeSort
  • FindMaximal
  • Correctness (Brief argument):
    • The rightmost element must be the maximal element
    • If the current element has a higher y value than any other element on the right side of it, it must be a maximum
    • If the current element has a lower y value than another point on the right of it, it is dominated by that point and thus cannot be a maximum