---
_id: '4064'
abstract:
- lang: eng
  text: Given a set of data points pi = (xi, yi ) for 1 ≤ i ≤ n, the least median
    of squares regression line is a line y = ax + b for which the median of the squared
    residuals is a minimum over all choices of a and b. An algorithm is described
    that computes such a line in O(n 2) time and O(n) memory space, thus improving
    previous upper bounds on the problem. This algorithm is an application of a general
    method built on top of the topological sweep of line arrangements.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Diane
  full_name: Souvaine, Diane
  last_name: Souvaine
citation:
  ama: Edelsbrunner H, Souvaine D. Computing least median of squares regression lines
    and guided topological sweep. <i>Journal of the American Statistical Association</i>.
    1990;85(409):115-119. doi:<a href="https://doi.org/10.1080/01621459.1990.10475313">10.1080/01621459.1990.10475313</a>
  apa: Edelsbrunner, H., &#38; Souvaine, D. (1990). Computing least median of squares
    regression lines and guided topological sweep. <i>Journal of the American Statistical
    Association</i>. American Statistical Association. <a href="https://doi.org/10.1080/01621459.1990.10475313">https://doi.org/10.1080/01621459.1990.10475313</a>
  chicago: Edelsbrunner, Herbert, and Diane Souvaine. “Computing Least Median of Squares
    Regression Lines and Guided Topological Sweep.” <i>Journal of the American Statistical
    Association</i>. American Statistical Association, 1990. <a href="https://doi.org/10.1080/01621459.1990.10475313">https://doi.org/10.1080/01621459.1990.10475313</a>.
  ieee: H. Edelsbrunner and D. Souvaine, “Computing least median of squares regression
    lines and guided topological sweep,” <i>Journal of the American Statistical Association</i>,
    vol. 85, no. 409. American Statistical Association, pp. 115–119, 1990.
  ista: Edelsbrunner H, Souvaine D. 1990. Computing least median of squares regression
    lines and guided topological sweep. Journal of the American Statistical Association.
    85(409), 115–119.
  mla: Edelsbrunner, Herbert, and Diane Souvaine. “Computing Least Median of Squares
    Regression Lines and Guided Topological Sweep.” <i>Journal of the American Statistical
    Association</i>, vol. 85, no. 409, American Statistical Association, 1990, pp.
    115–19, doi:<a href="https://doi.org/10.1080/01621459.1990.10475313">10.1080/01621459.1990.10475313</a>.
  short: H. Edelsbrunner, D. Souvaine, Journal of the American Statistical Association
    85 (1990) 115–119.
date_created: 2018-12-11T12:06:43Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-22T15:10:54Z
day: '01'
doi: 10.1080/01621459.1990.10475313
extern: '1'
intvolume: '        85'
issue: '409'
language:
- iso: eng
main_file_link:
- url: https://www.tandfonline.com/doi/abs/10.1080/01621459.1990.10475313
month: '01'
oa_version: None
page: 115 - 119
publication: Journal of the American Statistical Association
publication_identifier:
  eissn:
  - 1537-274X
  issn:
  - 0003-1291
publication_status: published
publisher: American Statistical Association
publist_id: '2059'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing least median of squares regression lines and guided topological sweep
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 85
year: '1990'
...