New techniques for computing order statistics in euclidean space: Extended abstract

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

Given a finite point-set S in E3, how hard is it to compute the Jtth largest interdistance, or say, the kt h largest slope or kth largest triangular area formed by points of S? We examine the complexity of a general class of problems built from these examples, and present a number of techniques for deriving nontrivial upper bounds. Surprisingly, these bounds often match or come very close to the complexity of the corresponding extremal problems (e.g.computing the largest or smallest interdistance, slope, etc.).

Original languageEnglish (US)
Title of host publicationProceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985
PublisherAssociation for Computing Machinery, Inc
Pages125-134
Number of pages10
ISBN (Electronic)0897911636, 9780897911634
DOIs
StatePublished - Jun 1 1985
Externally publishedYes
Event1st Annual Symposium on Computational Geometry, SCG 1985 - Baltimore, United States
Duration: Jun 5 1985Jun 7 1985

Publication series

NameProceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

Other

Other1st Annual Symposium on Computational Geometry, SCG 1985
CountryUnited States
CityBaltimore
Period6/5/856/7/85

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Geometry and Topology

Fingerprint Dive into the research topics of 'New techniques for computing order statistics in euclidean space: Extended abstract'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B. (1985). New techniques for computing order statistics in euclidean space: Extended abstract. In Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985 (pp. 125-134). (Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985). Association for Computing Machinery, Inc. https://doi.org/10.1145/323233.323251