Computing constrained minimum-width annuli of point sets

M. Berg, de, P. Bose, D. Bremner, S. Ramaswami, G. Wilfong

    Research output: Contribution to journalArticleAcademicpeer-review

    14 Citations (SciVal)


    We study the problem of determining whether a manufactured disk of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of the manufactured object, compute the thinnest annulus whose outer (or inner, or median) radius is r and that contains all the probe points. Our algorithms run in O(nlogn) time.
    Original languageEnglish
    Pages (from-to)267-275
    JournalComputer-Aided Design
    Issue number4
    Publication statusPublished - 1998


    Dive into the research topics of 'Computing constrained minimum-width annuli of point sets'. Together they form a unique fingerprint.

    Cite this