PARETO ENVELOPES IN SIMPLE POLYGONS

For a set T of n points in a metric space (X, d), a point y ∈ X is dominated by a point x ∈ X if d(x, t) ≤ d(y, t) for all t ∈ T and there exists t′ ∈ T such that d(x, t′) < d(y, t′). The set of non-dominated points of X is called the Pareto envelope of T. H. Kuhn (1973) established that in Euclidean spaces, the Pareto envelopes and the convex hulls coincide. Chalmet et al. (1981) characterized the Pareto envelopes in the rectilinear plane (ℝ2, d1) and constructed them in O(n log n) time. In this note, we investigate the Pareto envelopes of point-sets in simple polygons P endowed with geodesic d2- or d1-metrics (i.e., Euclidean and Manhattan metrics). We show that Kuhn's characterization extends to Pareto envelopes in simple polygons with d2-metric, while that of Chalmet et al. extends to simple rectilinear polygons with d1-metric. These characterizations provide efficient algorithms for construction of these Pareto envelopes.