Algorithms for bivariate medians and a Fermat-Torricelli problem for lines

Greg Aloupis, Stefan Langerman, Michael Soss, Godfried Toussaint

Research output: Contribution to journalArticlepeer-review

Abstract

Given a set S of n points in R 2, the Oja depth of a point θ is the sum of the areas of all triangles formed by θ and two elements of S. A point in R 2 with minimum depth is an Oja median. We show how an Oja median may be computed in O(nlog 3n) time. In addition, we present an algorithm for computing the Fermat-Torricelli points of n lines in O(n) time. These points minimize the sum of weighted distances to the lines. Finally, we propose an algorithm which computes the simplicial median of S in O(n 4) time. This median is a point in R 2 which is contained in the most triangles formed by elements of S.

Original languageEnglish (US)
Pages (from-to)69-79
Number of pages11
JournalComputational Geometry: Theory and Applications
Volume26
Issue number1
DOIs
StatePublished - Aug 2003

Keywords

  • Algorithms
  • Computational geometry
  • Estimators of location
  • Fermat-Torricelli problem
  • Geometric medians
  • Oja depth
  • Simplicial depth

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Algorithms for bivariate medians and a Fermat-Torricelli problem for lines'. Together they form a unique fingerprint.

Cite this