A fast and efficient algorithm for determining the connected orthogonal convex hulls

Nguyen Kieu Linh, Phan Thanh An and Tran Van Hoai

Applied Mathematics and Computation, 2022, vol. 429, issue C

Abstract: The Quickhull algorithm for determining the convex hull of a finite set of points was independently conducted by Eddy in 1977 and Bykat in 1978. Inspired by the idea of this algorithm, we present a new efficient algorithm, for determining the connected orthogonal convex hull of a finite set of points through extreme points of the hull, that still keeps advantages of the Quickhull algorithm. Consequently, our algorithm runs faster than the others (the algorithms introduced by Montuno and Fournier in 1982 and by An, Huyen and Le in 2020). We also show that the expected complexity of the algorithm is O(nlogn), where n is the number of points.

Keywords: Orthogonal convex hulls; Quickhull algorithm; Orthogonal convex sets; Orthogonal polygons; x−y convex hulls; Extreme points (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300322002570
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:429:y:2022:i:c:s0096300322002570

DOI: 10.1016/j.amc.2022.127183

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().