<?xml version="1.0" encoding="UTF-8"?>
<rss version="2.0"
	xmlns:content="http://purl.org/rss/1.0/modules/content/"
	xmlns:wfw="http://wellformedweb.org/CommentAPI/"
	xmlns:dc="http://purl.org/dc/elements/1.1/"
	xmlns:atom="http://www.w3.org/2005/Atom"
	xmlns:sy="http://purl.org/rss/1.0/modules/syndication/"
	xmlns:slash="http://purl.org/rss/1.0/modules/slash/"
	>

<channel>
	<title>Some stuff &#187; secant graph</title>
	<atom:link href="http://blog.yhuang.org/?feed=rss2&#038;tag=secant-graph" rel="self" type="application/rss+xml" />
	<link>https://blog.yhuang.org</link>
	<description>here.</description>
	<lastBuildDate>Wed, 27 Aug 2025 08:50:58 +0000</lastBuildDate>
	<language>en</language>
	<sy:updatePeriod>hourly</sy:updatePeriod>
	<sy:updateFrequency>1</sy:updateFrequency>
	<generator>http://wordpress.org/?v=3.1.1</generator>
		<item>
		<title>road path problem</title>
		<link>https://blog.yhuang.org/?p=242</link>
		<comments>https://blog.yhuang.org/?p=242#comments</comments>
		<pubDate>Fri, 19 Feb 2010 21:45:17 +0000</pubDate>
		<dc:creator>admin</dc:creator>
				<category><![CDATA[Uncategorized]]></category>
		<category><![CDATA[circle]]></category>
		<category><![CDATA[continuous path]]></category>
		<category><![CDATA[line]]></category>
		<category><![CDATA[math]]></category>
		<category><![CDATA[math 1]]></category>
		<category><![CDATA[pi math]]></category>
		<category><![CDATA[road]]></category>
		<category><![CDATA[secant graph]]></category>
		<category><![CDATA[theta]]></category>
		<category><![CDATA[unit radius]]></category>

		<guid isPermaLink="false">http://scripts.mit.edu/~zong/wpress/?p=242</guid>
		<description><![CDATA[Suppose there is a straight road, infinitely long at both ends, located 1 unit from your starting location. Find the most efficient path to reach the road, and the worst-case total length of this path. The trivial but wrong way is to go for 1 unit in some direction, then trace the circumference of a [...]]]></description>
			<content:encoded><![CDATA[<p>Suppose there is a straight road, infinitely long at both ends, located 1 unit from your starting location. Find the most efficient path to reach the road, and the worst-case total length of this path.</p>
<p>The trivial but wrong way is to go for 1 unit in some direction, then trace the circumference of a unit-radius circle. The road will surely be found this way, but the path length is \(1+2\pi\), which can be improved upon.<br />
<span id="more-242"></span><br />
Every possible position for the road corresponds to a tangent line to the unit circle centered at the starting location. Therefore, this is a problem about finding a shortest path that touches all tangent lines to a unit circle. To make this more concrete, let us transform the space into polar form as below.</p>
<p><img src="wp-content/uploads/images/roadpath2.png" /></p>
<p>We see that in polar form, the unit circle becomes the line \(r=1\) and each tangent line touching the circle at angle \(\theta_0\) becomes the graph \(r=\sec(\theta-\theta_0)\). The trivial solution corresponds to a path that traces \(r=0\) to \(r=1\) at \(\theta=0\), followed by \(\theta=0\) to \(\theta=2\pi\) at \(r=1\). This is not efficient.</p>
<p>In fact, any continuous path starting at \(r=0\) &#8220;reaches the road&#8221; (i.e. touches every tangent line) as long as it touches \(r=\sec(\theta)\) somewhere on \(\theta\in [0,\pi/2)\) and somewhere on \(\theta\in (3\pi/2,2\pi]\), and it stays above \(r=1\) between those two points. And up to shifts in \(\theta\), these are the only possible solutions.* Note that the path doesn&#8217;t need to be closed, like the trivial path was. So we are left to find the shortest such path (e.g. the one in green above).</p>
<p>Whereas in rectangular form, the shortest path between two points is a straight line, in polar form, the shortest path between two points is along a secant graph. It is a fairly easy matter to show that the shortest path must take the following form:</p>
<p>1. Start from \((r,\theta)=(0,\phi)\) for some \(\phi\in [0,\pi/2)\);<br />
2. Drop onto the graph \(r=\sec(\theta-2\phi)\), between the points \((r,\theta)=(\sec(\phi),\phi)\) and \((r,\theta)=(1,2\phi)\);<br />
3. Take the path \(r=1\) from \(\theta=2\phi\) to some \(\theta=2\pi-2\psi\);<br />
4. Drop onto the graph \(r=\sec(\theta-(2\pi-2\psi))\), between the points \((r,\theta)=(1,2\pi-2\psi)\) and \((r,\theta)=(\sec(2\pi-\psi),2\pi-\psi)\).</p>
<p>Finally, we need to solve two minimizations, which will find the best \(\phi\) and \(\psi\). \(\psi\) can actually be solved by inspection, but formally:</p>
\(\min_{\psi\in[0,\pi/2)} \tan(\psi) + \pi - 2\psi\)<br />
solution at \(\sec^2{\psi} = 2 \Rightarrow \psi=\pi/4\)
<p>\(\min_{\phi\in[0,\pi/2)} \sec(\phi) + \tan(\phi) + \pi - 2\phi\)<br />
solution at \(\frac{\sin(\phi)}{\cos^2(\phi)} + \sec^2(\phi) = 2 \Rightarrow \sin(\phi)=1/2 \Rightarrow \phi=\pi/6\).</p>
<p>The solved path has total length \(\tan(\pi/4) + \pi &#8211; \pi/2 + \sec(\pi/6) + \tan(\pi/6) + \pi &#8211; \pi/3 = 1+\sqrt{3}+7\pi/6\), and is plotted below. This is about 12% shorter than the trivial path.</p>
<p><img src="wp-content/uploads/images/roadpath.png" /></p>
<hr />
* Technically, we still need to prove that paths that re-enter the unit circle (go below \(r=1\)) are not worthy. One can reason about why such paths can be improved upon by replacing the path segments that re-enter the unit circle, but it seems a proof needs some global properties of the path. With the reader comment (below) about reflecting the starting point, the best path actually becomes a function \(r(\theta)\), of the variable \(\theta\), which almost certainly is a necessary condition for efficient paths. Then we can impose other constraints, like, \(\forall \theta_0: r(\theta) \not< \sec(\theta-\theta_0)\), which says the path function should not be dominated by any secant function (equivalent to crossing all tangent lines to the unit circle). This may be a direction to a complete proof.</p>
]]></content:encoded>
			<wfw:commentRss>https://blog.yhuang.org/?feed=rss2&#038;p=242</wfw:commentRss>
		<slash:comments>4</slash:comments>
		</item>
	</channel>
</rss>
