Convex hull of imprecise points in o(n n) time after preprocessing

DOI10.1145/1998196.1998199zbMATH Open1283.68360OpenAlexW2105434121MaRDI QIDQ5404402FDOQ5404402

Authors: Esther Ezra, Wolfgang Mulzer 

Publication date: 24 March 2014

Published in: Proceedings of the twenty-seventh annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1998196.1998199

Recommendations

• Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing
• Output-sensitive results on convex hulls, extreme points, and related problems
• Publication:4504027
• Largest and smallest convex hulls for imprecise points
• A linear algorithm for computing convex hulls for random lines

zbMATH Keywords

convex hullgeometric data structuresdata imprecisionplanar arrangementsrandomized constructions

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (5)

• Title not available (Why is that?)
• Delaunay triangulations of imprecise pointsin linear time after preprocessing
• Unions of onions: preprocessing imprecise points for fast onion layer decomposition
• Unions of onions: preprocessing imprecise points for fast onion decomposition
• Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing

This page was built for publication: Convex hull of imprecise points in \(o(n \log n)\) time after preprocessing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404402)