Tuesday, May 25, 2010

Packing Rectangles

Suppose that you have an n by n square made up of unit squares (we can think of this as a chessboard) on which you want to place R non-overlapping rectangles also made up of unit squares. How many ways can this be done? The board need not be covered.

There are many known variations of this problem, but the one that's most closely related that I can find solves this problem for R=1, in which case the answer is (n(n+1)/2)^2. I imagine that the problem has also been considered for general R, but can't seem to find it. Tips or ideas?

Wednesday, May 19, 2010


For those of you unfamiliar with the site, HollaBack NYC is a blog where people can submit (anonymously if they prefer) incidents of street harassment, often complete with a picture of the perp. The idea behind it is, of course, that no-one should have to accept street harassment as a given, and that it's good to have a way to, for your own sake and others', have a record of the harassment. It's somewhat of an institution, and has been around since 2005. Since then, it's grown into a larger movement and there are similar websites for other cities.

Now, they're planning to make it into an iPhone app (and are seeking funding). My understanding is that the app would partially serve the same purpose as the website, but in an easier, more immediate way - get harassed, use the app. It would also allow them to expand worldwide. But, more excitingly to me, it'll also serve as a means to collect data. How large is the problem? What neighborhoods/states/countries are the worst? What kinds of harassment are most common? How does time of day/ year change this? And could we see maps of that please?

If you're unfamiliar with the issue, or just with HollaBack itself, I definitely recommend taking a look at the site, or at least the FAQs.

Wednesday, May 12, 2010


It's official. I have a job for next year, and it's at Google. As seems to be their practice, I don't really know what I'll be doing, and won't until I get there, other than that I'll be a "Software Engineer." I suppose that's so I can't tell all of you! I'm hoping it's something nicely geometric, and maybe even something that relates to my research on kinetic sensor data. They certainly have a lot of changing data.

But, despite my theory bent, or perhaps because of doing mostly theory for the past few years, I'm excited to make something that people will actually use. The liberal arts student in me likes to learn about and do lots of different things, and I think I'll get to do that there. I was also really impressed with my interviewers - it seemed obvious that I'd learn a lot by working with people like them. Certainly, I won't be bored, and that's something I've been realizing lately is incredibly important to me.

I know many people may consider that this means I'm leaving research. Instead, I'd say that I'm going to be working on practical research. It will probably mean less papers, but more working systems. Research vs. Industry. It's a false dichotomy, or perhaps I just think it should be.