Controlled perturbation of sets of line segments in \(\mathbb R^2\) with smart processing order
type: Item
instance of: scholarly article
title: Controlled perturbation of sets of line segments in \(\mathbb R^2\) with smart processing order
zbMATH Open document ID: 1233.65022
author: Eli Packer
published in: Computational Geometry
publication date: 2011-06-17T00:00:00Z
review text: A controlled perturbation scheme for approximation of a set of line segments in the plane with fixed-precision number types is presented. The controlled perturbation scheme is based on an incremental perturbation of the line segment endpoints to eliminate potential degeneracies. First, the main idea and the suggested algorithm is presented. Then, the considered potential degeneracy cases are discussed and an upper bound of the perturbation magnitudes is derived. Next, sorting algorithms applied to the order determination of the processed endpoints are introduced and their modification for using in the suggested controlled perturbation scheme is described. Finally, experimental results obtained by the implemented algorithm are given and a significant decreasing in the perturbation magnitude in many cases is shown.
reviewed by: Ivana Linkeová
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 5909547
zbMATH Keywords: fixed-precision number
zbMATH Keywords: round-off error
zbMATH Keywords: geometric predicate
zbMATH Keywords: degeneracy
zbMATH Keywords: potential degeneracy
zbMATH Keywords: controlled perturbation
zbMATH Keywords: definite-degeneracy
zbMATH Keywords: sorting algorithm
zbMATH Keywords: line segments
MaRDI profile type: Publication
full work available at URL: j.comgeo.2010.12.002
OpenAlex ID: W2072599172
cites work: The computational geometry algorithms library CGAL
cites work: Aggregating inconsistent information
cites work: Polyhedral perturbations that preserve topological form
cites work: Approximation algorithms for spreading points
cites work: Ordering by weighted number of wins gives a good ranking for weighted tournaments
cites work: Combinatorial algorithms for feedback problems in directed graphs
cites work: Controlled perturbation for Delaunay triangulations
cites work: Q4198056
cites work: CONTROLLED PERTURBATION FOR ARRANGEMENTS OF CIRCLES
cites work: A perturbation scheme for spherical arrangements with application to molecular modeling
cites work: Classroom examples of robustness problems in geometric computations
cites work: Reliable and Efficient Computational Geometry Via Controlled Perturbation
DOI: 10.1016/J.COMGEO.2010.12.002
description: scientific article; zbMATH DE number 5909547