Smallest enclosing cylinders

E. Schömer, J. Sellen, M. Teichmann, Chee Yap

Research output: Contribution to journalArticle

Abstract

This paper addresses the complexity of computing the smallest-radius infinite cylinder that encloses an input set of n points in 3-space. We show that the problem can be solved in time O(n4 logO(1) n) in an algebraic complexity model. We also achieve a time of O(n4L · μ(L)) in a bit complexity model where L is the maximum bit size of input numbers and μ(L) is the complexity of multiplying two L bit integers. These and several other results highlight a general linearization technique which transforms nonlinear problems into some higher-dimensional but linear problems. The technique is reminiscent of the use of Plücker coordinates, and is used here in conjunction with Megiddo's parametric searching. We further report on experimental work comparing the practicality of an exact with that of a numerical strategy.

Original languageEnglish (US)
Pages (from-to)170-186
Number of pages17
JournalAlgorithmica (New York)
Volume27
Issue number2
DOIs
StatePublished - 2000

Keywords

  • Best-fit line
  • Geometric optimization
  • Parametric search
  • Smallest enclosing cylinder
  • ε-approximation algorithms

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Smallest enclosing cylinders'. Together they form a unique fingerprint.

  • Cite this

    Schömer, E., Sellen, J., Teichmann, M., & Yap, C. (2000). Smallest enclosing cylinders. Algorithmica (New York), 27(2), 170-186. https://doi.org/10.1007/s004530010011