### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985 |

Publisher | Association for Computing Machinery, Inc |

Pages | 125-134 |

Number of pages | 10 |

ISBN (Electronic) | 0897911636, 9780897911634 |

DOIs | |

State | Published - Jun 1 1985 |

Externally published | Yes |

Event | 1st Annual Symposium on Computational Geometry, SCG 1985 - Baltimore, United States Duration: Jun 5 1985 → Jun 7 1985 |

### Publication series

Name | Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985 |
---|

### Other

Other | 1st Annual Symposium on Computational Geometry, SCG 1985 |
---|---|

Country | United States |

City | Baltimore |

Period | 6/5/85 → 6/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