Smooth Voronoi Diagrams

The paper.js project has a cool demo with polygon smoothing on a Voronoi diagram. For fun I decided to implement my own version from scratch.

The first step was to implement a system for polygon smoothing using Bézier splines. Here is a demo of the technique (you can click/drag to interact with the demo). The blue points are the original polygon vertices. For the Bézier spline, the midpoints become the vertices and the original vertices become the control points (making this a quadratic Bézier spline).

To compute the Voronoi diagram polygons I used this excellent JavaScript library. Next, I computed polygon centroids using this formula. To create the gap between polygons I scaled the vertices towards each centroid. Here is the final demo: http://www.byronknoll.com/cells.html. The blue dots are the Voronoi seeds and the green dots are the polygon centroids. You can click to create new Voronoi seeds (or drag to move seeds).

I am not completely happy with the demo since there are some "jumps" in the animation when new vertices are added to a polygon. I tried several ideas to make the polygon smoothing more robust to adding vertices, but couldn't find anything I was happy with. Imagine adding a new polygon vertex exactly on top of an existing one. It doesn't change the shape of the original polygon, but it significantly changes the shape of the smoothed version using my algorithm. Intuitively it seems like something that would be easy to overcome, but I haven't been able to figure it out.

Response

In response to my last post, Jackie asks:

Not sure I understand your point about selling in as short a time window as possible. The day-to-day fluctuations of a stock's price is greater than its fluctuation over a week or so, right? But it might not be worth the extra transaction costs to sell over a time window.

I am replying here so the response is more widely visible. I claim that a stock should have much greater fluctuation at the end of a week than a day. In order to have less variance after a week, the stock would have to revert towards some sort of mean after the daily fluctuation. If this was true, I could use a simple strategy to make huge amounts of money in a short amount of time. I would look at a rolling average of one day for all stocks on the market. I would then buy the lowest stocks relative to their mean and then sell when their price hits the mean. The reason this strategy won't work is because stocks will not revert to a mean in the short-term. The reason they don't revert to a mean is because other investors in the market (especially high-frequency traders) would pick up on such an obvious pattern and take advantage of it. These traders would have a smoothing effect on stock price, ensuring that the price never reverts from the mean. Therefore I think it is necessary that variance increases the further into the future you consider.

Optimal Investment Strategies

I have recently become interested in the topic of investment. More specifically, I want to know:

1. When should I sell my Google stock? Should I sell it all in one chunk or spread out the sales over a time window?
2. How should I invest money that I currently have sitting in a bank?

I have been reading The Four Pillars of Investment for advice (as recommended by this post).

I was surprised to learn that there are actually provably optimal strategies when making these investment decisions. If you had asked me about this a month ago, I would have shrugged and said that it would be too complex to calculate an optimal strategy and that different experts in the field would probably give different answers. However, now I can say:

If you currently own stock in a single company (or a small set of companies), the optimal strategy is to sell immediately. The sale should be made as a single lump sum instead of spread out over a time window. You should then consider investing that money in an index fund.

The goal of investing money is to maximize expected profit for a given level of risk. The function of expected profit vs risk is monotonically increasing: with more risk you can always find an investment with higher expected profit. This fact can be used to make optimal investment decisions. If one investment has lower risk and higher expected reward than another investment, the optimal choice is clear. So, how can you calculate risk and reward?

It turns out that when investing in stocks, there is one fact that makes computing risk and expected reward much easier: regardless of how smart you are, you can not predict what a stock will do in the immediate future. You have zero information that is not already reflected in the stock price of a company. A company's stock price is a weighted average of a large number of expert investors. As with ensemble methods in machine learning, an individual can not compete with a weighted average of many expert predictors. Any investor who claims to be good at actively choosing a small set of stocks to invest in is wrong - even if they have an incredibly profitable investment history. In a room full of monkeys choosing to invest in random stocks, some of those monkeys would become rich due to natural variance in the profit distribution. I find this fact comforting - I am as good at predicting stock values as the best wall street investors (i.e. I can't).

There are certain exceptions to this:

• When new public information is released, you can try racing other investors to take advantage of the information (i.e. high-frequency trading) using an algorithm.
• In the long term, you know that the stock market as a whole will tend to revert to a mean value. It is profitable to invest more heavily during a bear market and sell during a bull market. Reverting to a mean does not apply to individual stocks in the short-term (otherwise it would be very easy to make money in the stock market).
• In the very long term, you know that all stocks eventually go to zero (i.e. all companies eventually go bankrupt).

It is known that different classes of stock have different levels of risk. A company on the brink of bankruptcy has high risk. As expected, riskier stocks tend to have higher expected profit (this can be verified by analyzing historical data, as done in The Four Pillars). So, let's assume you are interested in investing in a particular "class" of stocks (i.e. a set risk level). Within this class, you do not have the ability to pick out good stocks - the expected profit of all these stocks is the same. So, should you invest in a small set of stocks or a large set? Well, given a set expected profit, you should try to minimize risk. You can do this by decreasing the variance of your investment - splitting your investment among many companies has a lower profit variance than investing in few. So, the optimal strategy here is always to invest in a large number of companies (i.e. index funds).

So, back to my problem of selling stock in a single company. The optimal decision is to sell immediately since I can get the same expected profit with lower risk using an index fund. Now the question of whether to sell in a lump sum or to sell over a time window. Once again, the expected profit of these options is roughly the same since I can't predict what the stock will do in the future. Which option has lower risk? I conducted a poll among some friends and most of them argued that spreading the sale over a time window has lower risk since it will smooth out fluctuations in the stock price. However, I argue that a lump sum payment has much lower risk. The "fluctuations" in a stock price are not centered about some short-term mean - if they were it would be easy to take advantage of this to predict stock price. Instead, the longer your time window, the more variance there is in the expected stock price distribution (which has an expected value equal to the current stock price). This means the longer your time window, the more risk you incur. Therefore the optimal strategy is to minimize the time window (i.e. make a single lump-sum payment).

Now on to my second question of what to do with money in a bank. Even if I am completely risk averse, there exist investments with a higher expected value and lower risk than storing money in an account without interest rate. Due to inflation, I think most bank accounts actually have a negative expected value. As for my level of risk-aversion, I will probably work on constructing a portfolio with a mix of different classes of index funds and bonds. Once I have constructed a portfolio, the only maintenance it needs over time is rebalancing.

So, does anything here sound controversial to you? If so, please let me know - I am still new to this and could be completely wrong. But as far as I can tell, I can compute the optimal investment strategy when comparing a small set of options.

Space-Saving Algorithm

Peter Norvig recently posted an interesting article about the frequency of different ngrams in a massive data set. A few months ago I worked on a similar problem.

Inspired by Peter Norvig's post, I decided to release my code for the space-saving algorithm as an open source project: http://code.google.com/p/space-saving/

I optimized the speed of the program and tried testing it on Wikipedia. The file I used was a XML dump of Wikipedia which is 42,544,528,073 bytes (39.6 GiB). I used k=100,000,000 (100 million internal buckets). Here are the results:

• N=1
• N=2
• N=3
• N=4
• N=5
• N=10
• N=50
• N=100
• N=500
• N=1000

Unlike last time, the counts reported here are exact. After an initial pass with the space-saving algorithm my program makes a second pass to compute the exact counts for the top buckets.

I ended up implementing my own hash table from scratch for this project. I figure that since this problem has some unique properties (such as a constant number of elements in the hash table), it would be easier to optimize my own hash table rather than using something more generic. I used linear probing to resolve hash collisions.

I found a way to improve upon one aspect of the standard linear probing approach. Typically deleted entries are marked with a special label, so a large number of <delete,insert> swaps would eventually fill the table up with useless deletion entries (requiring an expensive resize). My implementation doesn't use deletion labels and never needs to be resized. Instead, when an entry is removed I propagate the empty spot down until it reaches a free slot. Performing this propagation operation requires computing the desired position of subsequent elements (to know whether the element can be moved) to maintain consistency. This can be done efficiently in my hash table since the elements are integers - computing the desired position just requires a mod operation.

Laservex Updates

Since the original Laservex launch I have been fixing many bugs and adding features. I recently added the most commonly request feature: dragging the center of a mirror. There are also now over 50 levels (mostly thanks to dllu and GuiltyBystander). So, if you haven't tried Laservex since the initial launch, I encourage you to try it again.

The site had a nice initial traffic spike from Reddit and Hacker News but traffic has been dropping recently. I regret launching/announcing the site so early in development, since during the traffic spike the game was buggier and harder to interact with (which probably lost many potential users).

Laservex Released!

I have finished implementing the game I have been working on for the last few weeks. Try it out at www.laservex.com.

Trip-Let

Here is a Trip-Let of my initials:

Printed using my brother's MakerBot Replicator.

laservex

I have started working on a new project: www.laservex.com. This will be a remake of a Java game I made a few years ago: http://byronknoll.com/lasers.html. This time I will implement it in HTML5 and support user-generated levels.

The Top-k Element Problem

I have been working on the problem of efficiently finding the most common items in a large stream of data. This problem shows up in many applications - I am working on it for a data compression project. One example application: given a stream of user queries to a search engine, find the top k queries which occur most often. Some Google employees published a fascinating algorithm for this problem called count sketch.

After reading through papers on the problem, I decided to use an algorithm called space-saving. I implemented it in C++ and have been testing it on the following task:

Problem: find the k most common substrings of length N in the Wikipedia database.

I haven't fully optimized my program yet, so I estimate it would currently take 4-5 days to process the 38GiB Wikipedia file I downloaded. I have some preliminary results on a subset of Wikipedia though - here is the output for k=1000 and N=1...30:

• N=1
• N=2
• N=3
• N=4
• N=5
• N=6
• N=7
• N=8
• N=9
• N=10
• N=11
• N=12
• N=13
• N=14
• N=15
• N=16
• N=17
• N=18
• N=19
• N=20
• N=21
• N=22
• N=23
• N=24
• N=25
• N=26
• N=27
• N=28
• N=29
• N=30

Each row has two columns (tab separated). The first column is the substring and the second column is the count.

Since the time complexity of this algorithm is completely independent of k, I actually chose k=1 million and then took the top 1000 from the million buckets. The heuristic I used for choosing k was to use the largest value possible such that the memory used by the program did not exceed the available RAM on my computer.

Five Player Go First Dice

In a previous post I proposed a challenge to come up with a set of go first dice for five players. I thought my prize would be safe since this seems like a difficult unsolved problem. Paul Vanetti has successfully won the challenge with the following solution:

• 0, 1, 2, 3, 4, 5, 6, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 259, 260, 261, 262, 263, 264, 265
• 7, 20, 21, 22, 35, 36, 37, 50, 83, 96, 97, 98, 111, 112, 113, 126, 139, 152, 153, 154, 167, 168, 169, 182, 215, 228, 229, 230, 243, 244, 245, 258
• 8, 12, 13, 14, 15, 19, 23, 27, 28, 29, 30, 34, 38, 42, 43, 44, 45, 49, 84, 88, 89, 90, 91, 95, 99, 103, 104, 105, 106, 110, 114, 118, 119, 120, 121, 125, 140, 144, 145, 146, 147, 151, 155, 159, 160, 161, 162, 166, 170, 174, 175, 176, 177, 181, 216, 220, 221, 222, 223, 227, 231, 235, 236, 237, 238, 242, 246, 250, 251, 252, 253, 257
• 9, 11, 16, 18, 24, 26, 31, 33, 39, 41, 46, 48, 85, 87, 92, 94, 100, 102, 107, 109, 115, 117, 122, 124, 141, 143, 148, 150, 156, 158, 163, 165, 171, 173, 178, 180, 217, 219, 224, 226, 232, 234, 239, 241, 247, 249, 254, 256
• 10, 17, 25, 32, 40, 47, 86, 93, 101, 108, 116, 123, 142, 149, 157, 164, 172, 179, 218, 225, 233, 240, 248, 255

These dice have the following number of faces:

• 90
• 32
• 72
• 48
• 24

When I described the problem in my original blog post I did not specify any constraint specifying that the dice need to have the same number of faces. This constraint is unnecessary because:

Conjecture: Given any valid set of N go first dice with number of faces x1, x2, ..., xN, it is always possible to generate a new set of go first dice with exactly LCM(x1, x2, ..., xN) faces per die.

This can be done using the following algorithm:

Suppose you have go first dice with the following labels:

• a1, a2, ..., aQ
• b1, b2, ..., bR
• ...
• y1, y2, ..., yZ

Let m = LCM(Q, R, ..., Z). The following should be a set of go first dice with m faces:

• m*a1, m*a1 + 1, ..., m*a1 + (m/Q) - 1, m*a2, m*a2 + 1, ..., m*a2 + (m/Q) - 1, m*aQ, m*aQ + 1, ..., m*aQ + (m/Q) - 1
• m*b1, m*b1 + 1, ..., m*b1 + (m/R) - 1, m*b2, m*b2 + 1, ..., m*b2 + (m/R) - 1, m*bR, m*bR + 1, ..., m*bR + (m/R) - 1
• ...
• m*y1, m*y1 + 1, ..., m*y1 + (m/Z) - 1, m*y2, m*y2 + 1, ..., m*y2 + (m/Z) - 1, m*yZ, m*yZ + 1, ..., m*yZ + (m/Z) - 1

Example of how to apply the algorithm to a simple set of dice (which are not go first dice):

• 1,2,4
• 3,5

LCM(3,2) = 6, so the merged dice are:

• 6*1, 6*1 + 1, 6*2, 6*2 + 1, 6*4, 6*4 + 1
• 6*3, 6*3 + 1, 6*3 + 2, 6*5, 6*5 + 1, 6*5 + 2

Which becomes:

• 6, 7, 12, 13, 24, 25
• 18, 19, 20, 30, 31, 32

Empty regions can be removed to form:

• 1, 2, 3, 4, 8, 9
• 5, 6, 7, 10, 11, 12

Since LCM(90, 32, 72, 48, 24) = 1440, Paul's solution can be used to generate a set of 5 go first dice with 1440 faces. Paul says he found a technique to use a solution for N-1 to generate N go first dice (I do not know how this is done). His technique can be used to quickly generate solutions for any N. The solutions generated by his algorithm are not optimal in terms of minimizing the number of faces on the dice.

Go First Dice Problem

The Problem:

I encountered an interesting riddle recently called the "go first dice problem". The challenge is to come up with a set of dice (one per player) such that:

• No two faces share the same label.
• The dice can be used to determine a fair turn order for the players after a single roll. That is, the player with the highest roll goes first, the second highest goes second, etc. A set of dice is fair if and only if every possible turn ordering is equally likely given random rolls.

More Information:

There are some stack exchange threads discussing the problem:

• math.stackexchange.com
• codegolf.stackexchange.com
• stackoverflow.com

Eric Harshbarger (puzzle designer/Lego sculptor/programmer/mathematician/Scrabble player) sells a set of 12 sided dice that solve the go first problem for four players: http://www.ericharshbarger.org/dice/#gofirst_4d12. As far as I know there is no known solution for five players. For fewer than five players:

• 2 players: minimum 2 faces
• 3 players: minimum 6 faces
• 4 players: minimum 12 faces

The Challenge:

Find a set of go first dice for five players. This will require at least 30 faces per die.

I have been working on trying to solve this (with a computer) for a few days. The search space is too large for a naïve brute-force search, so I think to make this computationally feasible you need to either:

• find a clever way to constrain the solution space (to make it small enough to exhaustively search), or
• come up with a heuristic so that your program is more likely to search in regions where a solution exists.

The Prize:

I will offer a small prize to whoever solves this challenge first. The prize will be a set of Eric's go first dice for four players - shipping paid by me to anywhere in the world. To claim the prize just email me with the solution and I will run a program to validate it. You can only claim the prize if you are actually the person who found the solution (e.g. don't copy it from someone). There is no set end date to this offer (as long as Eric continues selling the dice).

Metamoku

The first release of Metamoku is ready! Try it out at: www.metamoku.com

Metamoku should work across different browsers, operating systems, and devices (including smart phones and tablets). Let me know if you encounter problems on any platform. Note that you can also play team games if multiple people choose the same color. When I was developing the game I was unsure whether it would actually be fun or contain non-trivial strategies. After playing some test matches with friends I think the game does have some interesting strategic components (especially the team matches). I currently don't have any major features/tasks left to implement. I will probably continue tweaking gameplay parameters as I get more experience playing games.

Dark Souls PvP

I recently started my second playthrough of Dark Souls. Dark Souls is the best game I have ever played. I originally played Dark Souls on the PS3 - this time I am playing the PC port ("Prepare to Die" edition). That means now I can take screenshots!

Notice that the dragon's tail is missing - I did that.

Unhappy dragon.

This hallway is where I had an unforgettable experience. Another player had invaded my world to assassinate me (1v1 PvP). This is a pretty rare event when I play, so it is exciting when it happens. Luckily, this was the perfect place and time for him to invade - I had full health and the location could not be better. This narrow hallway leads to a dead-end, which means there is only one way in or out. That prevents my opponent from sneaking up with a surprise attack. My character is a pyromancer, which means that I am most effective at mid-range attacks. This hallway was perfect for my character because it forces the other player to walk directly into my spell range. So I waited in the hallway for him to attack. He spotted me from the end of the hallway and tried to lure me out - he can see my Pyromancy Flame so he knows that I have the advantage here. His weapon is some sort of dagger. Since I refuse to leave the hallway, eventually he cautiously approaches. When it looks like he is in my spell range, I start casting fire orbs at him. Impressively, he manages to stay far enough back to narrowly avoid my spells. When I advance he moves back, and when I move back he advances. So I continue casting the spell since I have plenty to spare. My spell is powerful enough that a single hit would make it very difficult for him to recover. Suddenly after one of my fire orbs misses him, he starts sprinting towards me. I cast another orb and it is headed directly at him. At the perfect time he does a dive roll under the orb and it narrowly misses him. He rolls past my side and stands up directly behind me. Before I have a chance to react he backstabs me and kills me with a single attack. The backstab attack is that powerful because it is so difficult to get directly behind a player. I was astounded at how perfect his sequence of moves was. As he was fading away to return to his world, he turned towards my corpse and bowed. I wish the battle had been recorded - it would have been fun to be able to watch it again.

Metamoku

I have started working on a new game! HTML5 canvas! Network multiplayer! Turn-based strategy! Metaballs!

The name of the game will be Metamoku. A combination of metaball and moku (which is territory in Go).

I have been putting together various demos to experiment with rendering metaballs. It is actually a difficult problem to render them fast+smooth+accurate. I have tried three approaches:

Approach	Speed	Smoothness	Accuracy
pair-wise Bézier curves	Fast	Good	Bad
pixel rendering	Variable	Bad	Good
border following	Slow	Good	Good

Pixel rendering is the most common rendering approach. However, it can get very slow on large displays. Also, making the edges smooth is difficult. dllu made a two color demo.

Here are a couple demos I made with the pair-wise approach. These are just an approximation to the actual metaball function and are therefore not "accurate".

I found a great article about the border following approach here. This is the most complex of the three approaches. I implemented a demo here. Here is another demo where you can see some of the path-finding internals (red is border misses, blue is border hits). These demos don't have real-time rendering or drag-and-drop because it is too slow. However, this approach might be feasible for a turn-based game with one frame per turn.

Password Management

The Problem:

• Using the same password on multiple websites is known to be insecure.
• Creating and remembering a different password for every website is difficult.

Solution:

My solution requires remembering two pieces of information:

1. A single secure key.
2. A simple string hashing function.

When registering for a website, generate your password by applying your hashing function to the domain name of the website (ignoring the top level domain) and append the output of that to your secure key. Voilà, you now only need to remember O(1) bits of information instead of O(N) to register N websites.

Example:

Step 1: generate and remember a single secure key. Let's say my key is now "0vDga5"

Step 2: generate and remember a string hashing function. Here is an example of a function to create a three character hash:

• Character 1: The first letter of the string.
• Character 2: The length of the string.
• Character 3: The last letter of the string.

Now when registering an account on the following websites, my password would be:

gmail.com: 0vDga5g5l

imdb.com: 0vDga5i4b

a.ca: 0vDga5a1a

subdomain.domain.xyz: 0vDga5d6n

Lossy Video Compression

Using a three dimensional DCT I can drop components from both the temporal and spatial dimensions. Here is what dropping high frequency temporal components looks like:

Lossy Audio Compression

Here is an experiment I ran performing lossy audio compression with DCT:


[link]

Audio Spectrogram

Using FFTW I made a program to visualize audio spectrograms. The song "Windowlicker" contains an image hidden in its spectrogram - here is the output from my program:

Discrete Cosine Transform

Today I spent a few hours playing with discrete cosine transforms using the FFTW library. I have been experimenting using DCT for lossy compression in different domains. Here is a visualization I made of lossy image compression using an increasing number of frequency components:


[link]

Elian Ambigram

Today I attempted to find an Elian ambigram. I wrote a small program to do a brute-force search through dictionary words to help. Out of all possible English words/phrases, it turns out only a handful of combinations are valid. The reason they are so rare is because Elian script has high rotational symmetry. The rotational symmetry adds constraints on how the ambigram can be constructed - standard Latin characters have far fewer constraints.