In this paper, we introduce a novel approach for efficiently computing the connected orthogonal convex hull \(\varvec{{{\,\textrm{COCH}\,}}(P)}\) of a finite set \(\varvec{P}\) of points in the 2D plane. By using a \(\varvec{(4k+4)}\) -sided orthogonal convex polygon \({\varvec{^{(4k+4)}{\mathcal {P}}}}\) constructed from 2k extremum directions, we can significantly reduce the input size by eliminating unnecessary interior points. This preprocessing step decreases the input size by up to 95% when \(\varvec{k=16}\) , leading to substantial improvements in computation time. Our method further enhances efficiency by partitioning the remaining points into \(\varvec{4k}\) subsets, classifying these subsets into four groups to identify type- \(\varvec{t}\) extreme points for \(\varvec{t=1, 2, 3, 4}\) , which allows for rapid identification of the extreme points of \(\varvec{{{\,\textrm{COCH}\,}}(P)}\) . Additionally, the algorithm is easily parallelizable and can scale up to \(\varvec{4k}\) parallel threads, resulting in remarkable speedups. Experimental results demonstrate that our algorithm outperforms state-of-the-art algorithms such as O-Quickhull (introduced by Linh et al. (Appl. Math. Comput. 429, 127183, 2022)) and O-Graham (introduced by An et al. (Appl. Math. Comput. 397, 125889, 2021)). For instance, with a dataset of \(\varvec{100,000,000}\) randomly generated points within a disc, our method achieved speedups of up to 16.23 times over O-Graham and 12.44 times over O-Quickhull. When parallelized, these speedup ratios increased significantly to 96.12 times over O-Graham and 73.68 times over O-Quickhull, highlighting the efficiency and scalability of our approach for high-demand computational applications.
