Two-line center problem from a polar view: A new algorithm and data structure

Jerzy W. Jaromczyk, Miroslaw Kowaluk

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

17 Scopus citations

Abstract

We present a new algorithm for the two-line center problem (also called unweighted orthogonal L-fit problem): "Given a set S of n points in the real plane, find two closed strips whose union contains all of the points and such that the width of the wider strip is minimized." An almost quadratic 0(n2 log2 n) solution is given. The previously best known algorithm for this problem has time complexity 0(n2log6n) and uses a parametric search methodology. Our solution applies a new geometric structure, anchored lower and upper chains, and is based on examining several constraint versions of the problem. The anchored lower and upper chain structure is of interest by itself and provides a fast response to queries that involve planar configurations of points. The algorithm does not assume the general position of the input data points.

Original languageEnglish
Title of host publicationAlgorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings
EditorsSelim G. Akl, Frank Dehne, Jörg-Rüdiger Sack, Nicola Santoro
Pages13-25
Number of pages13
DOIs
StatePublished - 1995
Event4th Workshop on Algorithms and Data Structures, WADS 1995 - Kingston, Canada
Duration: Aug 16 1995Aug 18 1995

Publication series

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

Conference

Conference4th Workshop on Algorithms and Data Structures, WADS 1995
Country/TerritoryCanada
CityKingston
Period8/16/958/18/95

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'Two-line center problem from a polar view: A new algorithm and data structure'. Together they form a unique fingerprint.

Cite this