Maximum stabbing line in 2D plane

Francis Y.L. Chin, Cao An Wang, Fu Lee Wang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)

Abstract

Two line estimator problems using the perpendicular and vertical distance measure are considered in this paper. (1) Given a set of n points in a plane, the line estimator problem is to determine a straight line which best fits this set of points. (2) Given a sequence of n points in a plane, the ordered line estimator problem is to determine a straight line which can best fit this set of points in order. Depending on the perpendicular/vertical distance measure, these two problems are related to the stabbing line problems of n circles/vertical line segments. With arrangement of curves, both problems can be solved in O(n2) and O(n3) time respectively.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings
EditorsShin-ichi Nakano, Hideki Imai, D.T. Lee, Takeshi Tokuyama, Takao Asano
Pages379-388
Number of pages10
DOIs
Publication statusPublished - 1999
Externally publishedYes
Event5th Annual International Conference on Computing and Combinatorics, COCOON 1999 - Tokyo, Japan
Duration: 26 Jul 199928 Jul 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1627
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th Annual International Conference on Computing and Combinatorics, COCOON 1999
Country/TerritoryJapan
CityTokyo
Period26/07/9928/07/99

Fingerprint

Dive into the research topics of 'Maximum stabbing line in 2D plane'. Together they form a unique fingerprint.

Cite this