A Lower Bound to Finding Convex Hulls
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that any algorithm in the quadratic decision-tree model must make cn log n tests for some input.
Abstract
article Free Access Share on A Lower Bound to Finding Convex Hulls Author: Andrew Chi-Chih Yao Computer Science Department, Stanford University, Stanford, California Computer Science Department, Stanford University, Stanford, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 28Issue 4pp 780–787https://doi.org/10.1145/322276.322289Published:01 October 1981Publication History 110citation1,250DownloadsMetricsTotal Citations110Total Downloads1,250Last 12 Months82Last 6 weeks20 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF