Friday, June 15, 2007

Tour de Fairport Harbor planning

Yes folks and loyal readers and viewers, it is another post from me, Dan Miller, your host in the crazy world of every whatever adventures. Or should that be Every Whatever adventures? After a few guest posts, we are back on the saddle. So no need to be confused about wondering why I'm going to be riding 63 buses in Houston, leaving my family and making all these plans without telling you. I don't know if anyone is sick of reading about Houston buses (I can only speak for myself in saying that I never tire of such talk) but this post is going to be bringing it back home to the Buckeye State.

Frankly, I don't know why I didn't think of this earlier. Sometime this summer we are going on vacation to the lovely 'burg of Fairport Harbor, Ohio. So recently I got the idea for TOUR DE FAIRPORT HARBOR 2007!!!! MWAHAHAHAHAHAHAH!!!!!

Okay, calming down now. FH is a pretty small town. Don't worry, further bulletins as events warrant, but I think it can be done in somewhere around 20-30 miles, maybe even less.

Because it's much smaller than Madeira, I am taking a more systematic approach. FH is mostly just in a grid layout, but it does have some wrinkles laid in. First I tried to figure out exactly where the boundaries of the village lie. This was actually a bit more complicated than I wish that it had been. I primarily used the Lake County auditor's website to try and figure it out. Using home sales as well as searches, I was able to (I think) come up with a fairly close enough boundary system. If you look at a map of Fairport Harbor, I am saying that, starting in the NW at Lake Erie and the Grand River, the border follows the Grand River south (on the east side of the river), then follows OH-535 north, with the village border continuing to follow East St. north (and also including the dead-end sections to the east of East St, such as Joughin St, York St, 3rd St, etc). I think this will be close enough to allow me to come up with a route, pending some investigation when I get there.

Some topics to research - where on OH-535 does FH start - at the river or slightly before / after? I did see that Windjammer Ct, just to the south of the river, is in Painesville Township. What about any part of N St Clair St, or any sections of OH 535 east of East St. What about Huntington Beach Drive - driveway to a park, or road? Then there's the always fun game of "Is this a road, or someone's driveway?"

So, now on to a bit of technical analysis of the problem. What we're looking for here is called an Eulerian path. That is, in technical terms, a path in a graph which visits each edge exactly once. Now we are not constrained in having to only visit each edge once, but obviously if we were able to do so, that would minimize our total distance, which IS the goal.

To find an Eulerian path through a graph (or in this case a road system), each vertex must have an even degree. Or, in other words, each intersection must have an even number of roads in it. So, 4-way intersections (or 6-ways!) are good, while T-intersections (3-way) or 5-ways are not.

I think it would be difficult to find a road system where this was the case, and Fairport Harbor is no exception. After printing out a map, I started plotting the "odd degree" vertices. To make the graph capable of containing an Eulerian path, you have to insert artificial edges between the odd degree vertices, thus making them even.

Note that for purposes of this experiment, I ignored dead-end / culdesac entries, since in those cases it is clear that you will have to do an out and back, which will turn it into even. As an example of this, take East St and Joughlin St (a dead-end st). It's currently a T-intersection (3 vertices or odd). But (barring starting or stopping the route on Joughlin), when you approach the intersection on East St. you will go out and back on Joughlin, creating a 2nd "edge" there, making it have 4 vertices or even. If this is not making sense to you, you should probably just go ahead and stop now (if you haven't already). An example of an odd vertex that we want to count is something like High St and Orchard St, or High St and King St.

So with that condition, I originally came up with 18 odd vertices. So it seemed simple that all I would have to do is connect them with 9 "extra" edges and I would have my path. But on further review, I realized that I was missing some instances where the out and backs on cul-de-sacs would throw things off. Just like doing an out and back on a cul-de-sac causes a 3-way intersection to be turned into a 4-way (and thus even and good), the out and back on a 4-way intersection causes it to be turned into a 5-way (and thus odd and bad). An example: East St and 3rd St. It's a 4-way intersection, but because you have to travel out and back on the section of 3rd st east of East St, that causes it to be a double edge and makes the vertex of East and 3rd into a 5-way.

So, when taking that into account, it comes up to 36 edges. While I'm sure it's just a coincidence that this is exactly twice the number, I'm not sure if it HAS to be an even number or not. I was trying to figure out what I would do if there was an odd number, but I'm not sure if it by definition HAS to be even or not. In any case, I just have to come up with 17 artificial edges, and the 17 that have the shortest distance, and I'll have my route. Note that it is 17 and not 18 because 2 of the odd vertices will be my starting and stopping points.

I will post later if/when I come up with a route, and of course a post for the report.

1 comment:

carey said...

The verticies are not the only thing that's odd :)