Efficient nearest-neighbor algorithm

I just thought this up last night: (math/CS warning)

Let’s say you have a large collection of points in a plane, and you need to find the closest point to point P. The obvious (and inefficient) way is to calculate the distance to every point, which requires N square roots and takes far too long to be useful in some cases (such as an early draft of Voronoid that didn’t work out because of this inefficiency). Here’s a better way I came up with:

  • For every point Q, calculate |xQ-xP| and |yQ-yP|. Find the sum and maximum of these values and store them.
  • Find the two points with the smallest sum and the smallest maximum.
  • If the same point has the smallest value for both, you win! That’s the closest point to P. Otherwise…
  • Go through the points again, using the stored values this time. For every point that has a smaller sum than that of the point with the smallest maximum and a smaller maximum than that of the point with the smallest sum, calculate the standard Euclidean distance from P: sqrt((xQ-xP)2+(yQ-yP)2). The closest point to P within this (likely very small) set of points is also the closest point overall.

I’m sure there are absurdly efficient algorithms for doing this better, but this one is very easy to implement (assuming it works, which I’ve sort of heuristically proven). In fact, I might go back and try my early version of Voronoid with this algorithm and see how it runs.

Doodling on an HTML5 canvas

I just tossed this together this morning. Next up: pretty colors!

(Note: Internet Explorer 8 or below can’t do canvases.)

“You have not discovered a potion for remembering, but for reminding”

I found an interesting quote today:

You have not discovered a potion for remembering, but for reminding; you provide your students with the appearance of wisdom, not with its reality. Your invention will enable them to hear many things without being properly taught, and they will imagine that they have come to know much while for the most part they will know nothing. And they will be difficult to get along with, since they will merely appear to be wise instead of really being so.

It could easily be about Wikipedia, Google, or the Internet in general.

Actually, it’s about a much older technology: writing. Specifically, it’s (Plato’s account of) Socrates’ (account of Thamus’) commentary on writing from Phaedrus. Full text here, via an interesting NY Times article on an AI Jeopardist.

What do you think? Was writing worth it? How about the Internet?

(Postscript: relevant comic from Chuck & Beans)

Voronoid: multiplayer puzzle game inspired by graph theory

Voronoid is my final project for CS50. It’s a colorful game based on Voronoi diagrams, with a twist — check it out!
Voronoid Screenshot

[Note: So far, Voronoid supports Chrome and Firefox, on any operating system. It may work in Opera, but probably won’t in IE or Safari.]

Firesheep is Scary! (And a Chrome/Firefox Solution)

Firesheep is a new Firefox plugin that makes it very, very, very easy for anyone to mess with your online accounts. It exploits the unbelievable lack of security in most websites.

One solution (and probably the easiest good one) is to use SSL encryption. That sounds complicated, but it’s usually as easy as entering “https://” instead of “http://” before the URL. I say “usually,” because not all websites support SSL (it’s much more complicated from their end!).

Of course, it’s a pain in the neck to type that in all the time, so here’s a quick solution for Chrome or Firefox. In either browser, it forces “s gmail.com” to redirect to “https://gmail.com/“, for example.

Chrome:
Wrench menu –> Options –> Basics tab –> Default Search section –> Manage –> Add…

Then add the following “search engine” keyword:

Name: SSL
Keyword: s
URL: https://%s

Firefox:
Bookmarks –> Organize Bookmarks –> Unsorted Bookmarks (in the sidebar)
Then Organize –> New Bookmark…

Then add:
Name: SSL
Location: https://%s
Keyword: s

Caveat:
This will force the first page you visit to use SSL, but the website may drop the security for future pages. For example, “s gmail.com” will stay encrypted, because Google is smart, but “s facebook.com” will go back to plain old HTTP after you log in, because Facebook…. isn’t that smart.

Plugins like HTTPS Everywhere (Firefox only, because of technical limitations in other browsers) will automate the process and keep your connection secure all the time.

Lame Joke

Knock Knock.

          Who’s there?

Man.

          man who

Life on Gliese 581g?

I don’t have time for a post, but man, this is exciting.

Astronomers have discovered an Earth-like planet in the “Goldilocks Zone” of its solar system. Gliese 581g is the sixth planet of the Gliese 581 system discovered to date, and the most promising of them all (others have received media attention for their size/composition, or location, but until now none have been squarely in the middle of the habitable zone).
More info from Science magazine; the paper itself will be in the next Astrophysical Journal.

In my opinion, Steve Vogt is getting carried away, misquoted, or just trying to make a name for himself with that “100% chance” soundbite; I haven’t heard anybody claim that the *only* prerequisite for life is a water-friendly temperature, and (although I’m no xenobiologist) the fact that 581g is a ribbon world doesn’t inspire confidence.

Still, this is the best shot at finding extraterrestrial life we’ve ever had. In the words of a friend-of-a-friend: “This is the coolest f***ing time to be alive.”

[EDIT] The fact that Gliese 581g is tidally locked is probably a good sign, as Vogt explains in the Space.com article. This provides more of a range of temperatures, from the blazingly-hot side facing the star to the frozen dark side. In between, there must therefore exist a fairly wide zone of Earthlike “Goldilocks” temperatures. A planet that rotates with respect to its sun has a much narrower range of temperatures, lowering the odds (although there is variation from the poles to the equator, of course!)

By the way, Space.com needs to work on their fact-checking. Mercury isn’t tide-locked, as scientists have known for decades [NASA].

Dissociated Press: All The King’s Men

Dissociated Press is a program included with the popular source-code editor Emacs. When run on a text file, it generates hilarious free-associations (see the link for details.)

It’s a wonderful toy, but it’s particularly good on something as rambling as Robert Penn Warren’s prose.

Behold:

I suppose that Anne, and juicy while Anne was inclined to bone and
muscle under flesh. Lois looked edible, and you knew it!" I
exclaimed, "I ought to have known it! It had to be."
"If you can guarantee results like that," I said, "you ought to have
it.
So the poor bastard had gone to the Other stroked the big leather
couch. The discomfort was due, in part at least, to the fact that the
summer, and the world, would ever end. But that morning when Anne
said that she wasn't accustomed to hear anything in pants talk like
that. Not that she didn't try to persuade me, but I got back, late at
night, and went to bed. The condom on the park path, the twitch in
the old bugger a little extra time before I popped the question to
him. He went out into the hal, Mr. Simms following. While Mr.
Simms locked the door, Cass said to him, for to fool. Well, this time
I'm going to fool somebody. I'm getting out of this race because you
admire his oratory."
"Ain't it?"
He didn't say anything to that.

A Plot-Motivated Theory of Time Travel

I’ve recently dreamed up a consistent model of time travel specifically designed to allow for good science fiction.

Up until now, I’ve typically used a branching-timeline model for the sake of simplicity, but it leaves much to desire in the way of plot: each time traveler finds themselves in their own, separate timeline, and there is eventually very little point in killing Hitler because he’s still alive in the original. To remedy that, I now introduce… [drumroll….]

The Ripple Model:
The central idea is an old cliche in lousy science fiction: you change the past, and the change propagates through the timeline until it hits the present. In most cases, it leads to absurdities like Back to the Future (“Oh my gawd, I’m fading! I have only hours of vaguely-defined metatime to make sure my parents meet, thereby leading to my conception, which is apparently not already guaranteed because only I have free will in this movie!”)

However, this approach can be made rigorous. Consider the following:

You leave 2010 and appear instantly (meaning that no subjective time passes) in 1930 in Germany. You shoot Hitler and immediately leave for France, 1940. Twenty seconds later, the world changes around you: the war-torn nation is replaced by a happy pastoral scene, but you are unaffected because your own history (starting from 2010 and including the time travel) is intact. You jump to the present, and find that WWII still happened. Seventy seconds later, the encyclopedia entry in front of you disappears, but you hardly notice, because a tiny fraction of a second after that, the ripple swallows your own remaining history and you disappear. Nearby, an alternative version of you that has never heard of Hitler or WWII carries on.
Continue reading

Short Story: Theoretical

Note: This story borrows the character of Doc Labyrinth from Philip K Dick’s fantastic short stories. For the real thing, check out “The Short Happy Life of the Brown Oxford” or “The Preserving Machine”.

“What is it, Doc?”

Doc Labyrinth furrowed his brow and tapped his desk pensively. “That’s the trouble! I can’t remember.”

Sighing, I pulled out a chair and sat down. My friend was brilliant — no question about it — but more than slightly scatterbrained. I’m still not sure exactly what sort of doctorate he has.

“How do you know there’s a problem if you can’t remember what it is?”

“Well, I know what the problem is, in the general sense. I just don’t have any specifics.” He paused with the momentary hesitation that precedes all of his technical explanations. “You are aware that I have been studying Taoist philosophy?”
Continue reading