Approximate ESPs on surfaces of polytopes using a rubberband algorithm

Fajie Li*, Reinhard Klette, Xue Fu

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    Abstract

    Let p and q be two points on the surface of a polytope Pi. This paper provides a rubberband algorithm for computing a Euclidean shortest path between p and q (a so-called surface ESP) that is contained on the surface of Pi. The algorithm has k(1)(epsilon).k(2)(epsilon).O(n(2)) time complexity, where n is the number of vertices of Pi, k(i)(epsilon) = (L-0i - L-i)/epsilon, for the true length L-i of some shortest path with initial (polygonal path) length L-0i (used when approximating this shortest path), for i = 1, 2. Rubberband algorithms follow a straightforward design strategy, and the proposed algorithm is easy to implement and thus of importance for applications, for example, when analyzing 3D objects in 3D image analysis, such as in biomedical or industrial image analysis, using 3D image scanners.

    Original languageEnglish
    Title of host publicationADVANCES IN IMAGE AND VIDEO TECHNOLOGY, PROCEEDINGS
    EditorsD Mery, L Rueda
    Place of PublicationBERLIN
    PublisherSpringer
    Pages236-247
    Number of pages12
    ISBN (Print)978-3-540-77128-9
    Publication statusPublished - 2007
    Event2nd IEEE Pacific Rim Symposium on Video and Technology - , Chile
    Duration: 17-Dec-200719-Dec-2007

    Publication series

    NameLECTURE NOTES IN COMPUTER SCIENCE
    PublisherSPRINGER-VERLAG BERLIN
    Volume4872
    ISSN (Print)0302-9743

    Other

    Other2nd IEEE Pacific Rim Symposium on Video and Technology
    CountryChile
    Period17/12/200719/12/2007

    Keywords

    • rubberband algorithm
    • Euclidean shortest path
    • surface ESP
    • SHORTEST PATHS

    Cite this