skip to main content
10.1145/1247069.1247120acmconferencesArticle/Chapter ViewAbstractPublication PagessocgConference Proceedingsconference-collections
Article

Pareto envelopes in R3 under l1 and l distance functions

Published: 06 June 2007 Publication History

Abstract

Given a vector objective function f = (f1,...,fn) defined on a set X, a point y∈X is dominated by a point x∈ X if fi(x) < fi(y) forall i∈(1,...,n) and there exists an index j∈(1,...,n) such that fj(x) < fj(y). The non-dominated pointsof X are called the Pareto optima of f. H. Kuhn(1973) applied the concept of Pareto optimality to distancefunctions and characterized the convex hull conv (T) of any set T=(t1,...,tn) of Rm as the set of all Paretooptima of the vector function d2(x)=(d2(x,t1),...,d2(x,tn)), where d2(x,y)is the Euclidean distance between x,y∈ Rm. Motivatedby this result, given a set T=(t1,...,tn) of points of ametric space (X,d), we call the set Pd(T) of all Paretooptima of the function d(x)=(d(x,t1),...,d(x,tn)) the Pareto envelope of T. In this paper, we investigate the Pareto envelopes in Rm endowed with l1- or l-distances. We characterize PI(T) in all dimensions and PM(T) in R3. Usingthese results, we design efficient algorithms for constructing theseenvelopes in R3, in particular, an optimal O(n logn)-time algorithm for PM(T) and an O(n log2n)-time algorithmfor PI(T).

References

[1]
H.-J. Bandelt and V. Chepoi, Metric graph theory and geometry: a survey. Contemp. Math. (to appear).
[2]
J.-D. Boissonnat and M. Yvinec, Géométrie Algorithmique, Ediscience International, Paris, 1995.
[3]
J.-D. Boissonnat, M. Sharir, B. Tagansky, and M. Yvinec, Voronoi diagrams in higher dimensions under certain polyhedral distance functions, Discr. Comput. Geom. 19(1998), 485--519.
[4]
V. Boltyanski, H. Martini, and P. S. Soltan, Excursions into Combinatorial Geometry, Springer, Berlin, 1997.
[5]
G. Chalmet, L. Francis, and A. Kolen, Finding efficient solutions for rectilinear distance location problems efficiently, Europ. J. Oper. Res. 6 (1981), 117--124.
[6]
V. Chepoi, K. Nouioua, Y.Vaxès, A rounding algorithm for approximating minimum Manhattan networks, In APPROX-RANDOM'2005, pp. 40--51.
[7]
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, and M. H. Overmars, Computational Geometry : Algorithms and Applications, 2000, Springer-Verlag, Berlin.
[8]
M. de Berg, Ray Shooting, Depth Orders and Hidden Surface Removal, 1993, Springer-Verlag, Berlin.
[9]
A. W. M. Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups : a note on combinatorial properties of metric spaces. Adv. Math., 53 (1984), 321--402.
[10]
R. Durier, On Pareto optima, the Fermat-Werber problem, and polyhedral gauges. Math. Progr. 47 (1990), 65--79.
[11]
R. Durier and C. Michelot, Sets of efficient points in normed space, J. Math. Analys. Appl. 117 (1986), 506--528.
[12]
P. Hansen, T. Perreur, and J.F. Thisse, Location theory, dominance and convexity : some further results. Oper. Res. 28 (1980), 1241--1250.
[13]
J.R. Isbell, Six theorems about metric spaces. Comment. Math. Helv. 39 (1964), 65--74.
[14]
H. W. Kuhn, A note on Fermat's problem, Math. Prog. 4 (1973), pp98--107.
[15]
K. Nouioua, Enveloppes de Pareto et Réseaux de Manhattan: caractérisations et algorithmes, Thèse de Doctorat en Informatique, Université de la Méditerranée, 2005.
[16]
B. Pelegrin and F.R. Fernandez, Determination of efficient points in multiple-objective location problems, Nav. Res. Logistics 35 (1988), 697--705.
[17]
J. T. Schwartz and M. Sharir, On the two--dimensional Davenport-Schinzel problem, J. Symbolic Comput. 10 (1990), 371--393.
[18]
R. E. Steuer, Multiple Criteria Optimization: Theory, Computation and Application, Wiley, New York, 1986.
[19]
B. Sturmfels and J. Yu, Classification of six-point metrics, Electr. J. Combin., 11 (2004).
[20]
J.F. Thisse, J.E. Ward, and R.E. Wendell, Some properties of location problems with block and round norms. Oper. Res. 32 (1984), 1309--1327.
[21]
M. van de Vel, Theory of Convex Structures, Elsevier, Amsterdam, 1993.
[22]
M. van de Vel, Determination of msd(Ln). J. Algebr. Combin. 9 (1999), 161--171.
[23]
R.E. Wendell and A.P. Hurter, Location theory, dominance, and convexity. Oper. Res. 21 (1973), 314--320.
[24]
R. E. Wendell, A.P. Hurter, and T.J. Lowe, Efficient points in location theory. AIEE Trans. 9 (1973), 238--246.
[25]
P. Widmayer, Y. F. Wu, and C. K. Wong, On some distance problems in fixed orientations. SIAM J. Comput. 16 (1987), 728--746.

Cited By

View all

Index Terms

  1. Pareto envelopes in R3 under l1 and l distance functions

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SCG '07: Proceedings of the twenty-third annual symposium on Computational geometry
    June 2007
    404 pages
    ISBN:9781595937056
    DOI:10.1145/1247069
    • Program Chair:
    • Jeff Erickson
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 06 June 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Pareto envelope
    2. algorithm
    3. dominance
    4. l1- and linf-distance

    Qualifiers

    • Article

    Acceptance Rates

    Overall Acceptance Rate 625 of 1,685 submissions, 37%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 13 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media