@misc{aghamolaei_computing_2026,
	title = {Computing {Planar} {Convex} {Hulls} with a {Promise}},
	url = {http://arxiv.org/abs/2605.03904},
	doi = {10.48550/arXiv.2605.03904},
	abstract = {Computing the convex hull of a planar n-point set P is one of the most fundamental problems in computational geometry. It has an Ω(n log n) lower bound in the algebraic computation tree model of computation, and there are many convex hull algorithms that achieve this running time. Classical results in computational geometry show that under special input assumptions it becomes possible to achieve sub-O(n log n) time algorithms to compute the convex hull. For instance, when the points are given as a sequence in lexicographical or angular order, the convex hull can be computed in linear time. Even under the weaker assumption that the sequence of points corresponds to the ordered vertices of a simple polygonal chain, linear-time algorithms exist.},
	language = {en},
	urldate = {2026-05-12},
	publisher = {arXiv},
	author = {Aghamolaei, Sepideh and Buchin, Kevin and Chan, Timothy M. and Conradi, Jacobus and Hoog, Ivor Van der and Keikha, Vahideh and Phillips, Jeff M. and Raichel, Benjamin},
	month = may,
	year = {2026},
	note = {arXiv:2605.03904 [cs.CG]},
	keywords = {Computer Science - Computational Geometry, SYS: CosmicAI Contact Author, WG: Observable},
}

{"_id":"8J6WCq3GqLRaeFF3N","bibbaseid":"aghamolaei-buchin-chan-conradi-hoog-keikha-phillips-raichel-computingplanarconvexhullswithapromise-2026","author_short":["Aghamolaei, S.","Buchin, K.","Chan, T. M.","Conradi, J.","Hoog, I. V. d.","Keikha, V.","Phillips, J. M.","Raichel, B."],"bibdata":{"bibtype":"misc","type":"misc","title":"Computing Planar Convex Hulls with a Promise","url":"http://arxiv.org/abs/2605.03904","doi":"10.48550/arXiv.2605.03904","abstract":"Computing the convex hull of a planar n-point set P is one of the most fundamental problems in computational geometry. It has an Ω(n log n) lower bound in the algebraic computation tree model of computation, and there are many convex hull algorithms that achieve this running time. Classical results in computational geometry show that under special input assumptions it becomes possible to achieve sub-O(n log n) time algorithms to compute the convex hull. For instance, when the points are given as a sequence in lexicographical or angular order, the convex hull can be computed in linear time. Even under the weaker assumption that the sequence of points corresponds to the ordered vertices of a simple polygonal chain, linear-time algorithms exist.","language":"en","urldate":"2026-05-12","publisher":"arXiv","author":[{"propositions":[],"lastnames":["Aghamolaei"],"firstnames":["Sepideh"],"suffixes":[]},{"propositions":[],"lastnames":["Buchin"],"firstnames":["Kevin"],"suffixes":[]},{"propositions":[],"lastnames":["Chan"],"firstnames":["Timothy","M."],"suffixes":[]},{"propositions":[],"lastnames":["Conradi"],"firstnames":["Jacobus"],"suffixes":[]},{"propositions":[],"lastnames":["Hoog"],"firstnames":["Ivor","Van","der"],"suffixes":[]},{"propositions":[],"lastnames":["Keikha"],"firstnames":["Vahideh"],"suffixes":[]},{"propositions":[],"lastnames":["Phillips"],"firstnames":["Jeff","M."],"suffixes":[]},{"propositions":[],"lastnames":["Raichel"],"firstnames":["Benjamin"],"suffixes":[]}],"month":"May","year":"2026","note":"arXiv:2605.03904 [cs.CG]","keywords":"Computer Science - Computational Geometry, SYS: CosmicAI Contact Author, WG: Observable","bibtex":"@misc{aghamolaei_computing_2026,\n\ttitle = {Computing {Planar} {Convex} {Hulls} with a {Promise}},\n\turl = {http://arxiv.org/abs/2605.03904},\n\tdoi = {10.48550/arXiv.2605.03904},\n\tabstract = {Computing the convex hull of a planar n-point set P is one of the most fundamental problems in computational geometry. It has an Ω(n log n) lower bound in the algebraic computation tree model of computation, and there are many convex hull algorithms that achieve this running time. Classical results in computational geometry show that under special input assumptions it becomes possible to achieve sub-O(n log n) time algorithms to compute the convex hull. For instance, when the points are given as a sequence in lexicographical or angular order, the convex hull can be computed in linear time. Even under the weaker assumption that the sequence of points corresponds to the ordered vertices of a simple polygonal chain, linear-time algorithms exist.},\n\tlanguage = {en},\n\turldate = {2026-05-12},\n\tpublisher = {arXiv},\n\tauthor = {Aghamolaei, Sepideh and Buchin, Kevin and Chan, Timothy M. and Conradi, Jacobus and Hoog, Ivor Van der and Keikha, Vahideh and Phillips, Jeff M. and Raichel, Benjamin},\n\tmonth = may,\n\tyear = {2026},\n\tnote = {arXiv:2605.03904 [cs.CG]},\n\tkeywords = {Computer Science - Computational Geometry, SYS: CosmicAI Contact Author, WG: Observable},\n}\n\n\n\n","author_short":["Aghamolaei, S.","Buchin, K.","Chan, T. M.","Conradi, J.","Hoog, I. V. d.","Keikha, V.","Phillips, J. M.","Raichel, B."],"key":"aghamolaei_computing_2026","id":"aghamolaei_computing_2026","bibbaseid":"aghamolaei-buchin-chan-conradi-hoog-keikha-phillips-raichel-computingplanarconvexhullswithapromise-2026","role":"author","urls":{"Paper":"http://arxiv.org/abs/2605.03904"},"keyword":["Computer Science - Computational Geometry","SYS: CosmicAI Contact Author","WG: Observable"],"metadata":{"authorlinks":{}}},"bibtype":"misc","biburl":"https://bibbase.org/zotero-group/pratikmhatre/5933976","dataSources":["yJr5AAtJ5Sz3Q4WT4"],"keywords":["computer science - computational geometry","sys: cosmicai contact author","wg: observable"],"search_terms":["computing","planar","convex","hulls","promise","aghamolaei","buchin","chan","conradi","hoog","keikha","phillips","raichel"],"title":"Computing Planar Convex Hulls with a Promise","year":2026}