𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The shortest path in a simply-connected domain having a curved boundary

✍ Scribed by S. Bharath Ram; M. Ramanathan

Book ID
104006515
Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
725 KB
Volume
43
Category
Article
ISSN
0010-4485

No coin nor oath required. For personal study only.

✦ Synopsis

Given two distinct points S and E on a closed parametric curve forming the boundary of a simplyconnected domain (without holes), this paper provides an algorithm to find the shortest interior path (SIP) between the two points in the domain. The SIP consists of portions of curves along with straight line segments that are tangential to the curve. The algorithm initially computes point-curve tangents and bitangents using their respective constraints. They are then analyzed further to identify potential tangents. A region check is performed to determine the tangent that will form part of the SIP. Portions of the curve that belong to the SIP are also identified during the process. The SIP is identified without explicitly computing the length of the curves/tangents. The curve is represented using non-uniform rational B-splines (NURBS). Results of the implementation are provided.

πŸ“œ SIMILAR VOLUMES

On the complexity of finding paths in a
On the complexity of finding paths in a two-dimensional domain I: Shortest paths
✍ Arthur W. Chou; Ker-I Ko πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 342 KB πŸ‘ 2 views

## Abstract The computational complexity of finding a shortest path in a two‐dimensional domain is studied in the Turing machine‐based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial‐time computable two‐dimensional do