An Optimal-Time Algorithm for Slope Selection

descriptionPublicationkeyboard_double_arrow_right Article 01 Aug 1989 English Publisher:Society for Industrial & Applied Mathematics (SIAM)Journal:SIAM Journal on Computing, volume 18, pages 792-810 (issn: 0097-5397, eissn: 1095-7111,

Copyright policy )

Authors: Richard Cole 0001; Jeffrey S. Salowe; William L. Steiger; Endre Szemerédi;

doi: 10.1137/0218055

An Optimal-Time Algorithm for Slope Selection

- Summary
- Subjects
- Metrics

Abstract

The paper contributes to geometric selection problems. The main emphasis is on developing optimal algorithm for computing the k-th largest (smallest) slope determined by given plane point-set. The algorithm makes use of parametric search technique of \textit{N. Megiddo} [J. Assoc. Comput. Mach. 30, 852-865 (1983; Zbl 0627.68034)] with the very interesting improvement by means of approximate ranking.

Related Organizations

Rutgers, The State University of New Jersey
United States
University of Virginia
United States
Hungarian Academy of Sciences
Hungary
New York University
United States

Keywords

Information storage and retrieval of data, Analysis of algorithms and problem complexity, slope selection, computational geometry, Searching and sorting, parametric search

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	75
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%