On the recognition of digital circles in linear time

DOI10.1016/0925-7721(93)90025-2MaRDI QIDQ1803274zbMATH OpenOpenAlexFDO

Authors P. W. Sauer

Publication date 29 June 1993

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0925-7721(93)90025-2

zbMATH Keywords

circledigitizationFreeman code

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computing methodologies for image processing (68U10)

Review text

The author proves that it is possible to decide if a set of \(N\) points of a grid comes from the perfect digitization of a circle in \(O(N)\) steps.

Recommendations

• The linear time recognition of digital arcs
• Linear-time recognition of circular-arc graphs
• A simpler linear-time recognition of circular-arc graphs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• On Three Constrained Versions of the Digital Circular Arc Recognition Problem
• An efficient randomized algorithm for detecting circles
• Measure of circularity for parts of digital boundaries and its fast computation
• Recognizing circle graphs in polynomial time
• Discrete Geometry for Computer Imagery
• Fast recognition of a digital straight line subsegment: two algorithms of logarithmic time complexity

Cites work

• A bibliography on digital and computational convexity (1961-1988)
• Digital Straight Line Segments
• scientific article; zbMATH DE number 45315 (Why is no real title available?)
• scientific article; zbMATH DE number 48159 (Why is no real title available?)
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
• On the Chain Code of a Line

Cited in

(9)

• Determining digital circularity using integer intervals
• Fast circular arc segmentation based on approximate circularity and cuboid graph
• Digital circles, spheres and hyperspheres: from morphological models to analytical characterizations and topological properties
• On Three Constrained Versions of the Digital Circular Arc Recognition Problem
• Topological relations between separating circles
• Algorithmic detection of hypercircles
• Digital straightness, circularity, and their applications to image analysis
• A unified scheme for detecting fundamental curves in binary edge images
• Least squares fitting of digital polynomial segments

This page was built for publication: On the recognition of digital circles in linear time

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