Abstract
Many surgical procedures could benefit from guiding a bevel-tip needle along circular arcs to multiple treatment points in a patient. At each treatment point, the needle can inject a radioactive pellet into a cancerous region or extract a tissue sample. Our main result is an algorithm to steer a bevel-tip needle through a sequence of treatment points in the plane while minimizing the number of times that the needle must be reoriented. This algorithm is related to [6] and takes quadratic time when consecutive points in the sequence are sufficiently separated. We can also guide a needle through an arbitrary sequence of points in the plane by accounting for a lack of optimal substructure.
This work has been supported by NSF CAREER CCF-0643597, CCF-0635013, and the 2009 University of Texas at San Antonio Presidential Dissertation Fellowship.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, P.K., Biedl, T., Lazard, S., Robbins, S., Suri, S., Whitesides, S.: Curvature-constrained shortest paths in a convex polygon. In: 14th Symposium on Computational Geometry (SoCG), pp. 392–401 (1998)
Alterovitz, R., Branicky, M., Goldberg, K.: Motion planning under uncertainty for image-guided medical needle steering. International Journal of Robotics Research 27(1361) (2008)
Alterovitz, R., Goldberg, K., Okamura, A.: Planning for steerable bevel-tip needle insertion through 2d soft tissue with obstacles. In: IEEE International Conference on Robotics and Automation, pp. 1640–1645 (2005)
Bereg, S., Kirkpatrick, D.: Curvature-bounded traversals of narrow corridors. In: 21st Symposium on Computational Geometry (SoCG), pp. 278–287 (2005)
Cook IV, A.F., Wenk, C.: Link distance and shortest path problems in the plane. In: Goldberg, A.V., Zhou, Y. (eds.) AAIM 2009. LNCS, vol. 5564, pp. 140–151. Springer, Heidelberg (2009)
Dror, M., Efrat, A., Lubiw, A., Mitchell, J.S.B.: Touring a sequence of polygons. In: 35th ACM Symposium on Theory of Computing (STOC), pp. 473–482 (2003)
Dubins, L.E.: On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. American Journal of Mathematics 79(3), 497–516 (1957)
Duindam, V., Xu, J., Alterovitz, R., Sastry, S., Goldberg, K.: 3d motion planning algorithms for steerable needles using inverse kinematics. In: Eighth International Workshop on Algorithmic Foundations of Robotics, WAFR (2008)
Maheshwari, A., Sack, J.-R., Djidjev, H.N.: Link distance problems. In: Handbook of Computational Geometry (1999)
Mitchell, J.S.B., Rote, G., Woeginger, G.J.: Minimum-link paths among obstacles in the plane. In: 6th Symposium on Computational Geometry (SoCG), pp. 63–72 (1990)
Xu, J., Duindam, V., Alterovitz, R., Goldberg, K.: Motion planning for steerable needles in 3d environments with obstacles using rapidly-exploring random trees and backchaining. In: IEEE Conference on Automation Science and Engineering, CASE (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bitner, S., Cheung, Y.K., Cook, A.F., Daescu, O., Kurdia, A., Wenk, C. (2010). Visiting a Sequence of Points with a Bevel-Tip Needle. In: López-Ortiz, A. (eds) LATIN 2010: Theoretical Informatics. LATIN 2010. Lecture Notes in Computer Science, vol 6034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12200-2_43
Download citation
DOI: https://doi.org/10.1007/978-3-642-12200-2_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12199-9
Online ISBN: 978-3-642-12200-2
eBook Packages: Computer ScienceComputer Science (R0)