Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing
type: Item
instance of: scholarly article
title: Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing
zbMATH Open document ID: 1262.65031
author: Esther Ezra
author: Wolfgang Mulzer
published in: Computational Geometry
publication date: 2013-03-07T00:00:00Z
review text: Given a set of planar regions, each of which represents an estimate about an input point, and the exact coordinates of the points arrive some time later and need to be processed quickly. Under certain assumption, the authors show that one can preprocess the input lines \(L\) such that given any set \(P\) of points, each of which lies on a distinct line of \(L\), the corresponding convex hull can be computed in expected time \(O(n \alpha (n) )\), where \(\alpha (.)\) is the inverse Ackermann function [\textit{J. Basch} et al., J. Algorithms 31, No. 1, 1--28 (1999; Zbl 0928.68034)]. The authors' data structure has quadratic preprocessing time and storage and the convex hull algorithm is based on a batched randomized incremental construction similar to Seidel's tracing technique [\textit{R. Seidel}, Comput. Geom. 1, No. 1, 51--64 (1991; Zbl 0733.68092)].
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 6142832
zbMATH Keywords: data imprecision
zbMATH Keywords: convex hull
zbMATH Keywords: planar arrangements
zbMATH Keywords: geometric data structure
zbMATH Keywords: algorithm
reviewed by: H. P. Dikshit
MaRDI profile type: Publication
full work available at URL: j.comgeo.2012.03.004
OpenAlex ID: W1589450195
DOI: 10.1016/J.COMGEO.2012.03.004
description: scientific article; zbMATH DE number 6142832