The dynamic map labelling problem

Call the problem of displaying a user-defined, mutable subset of items on a map the dynamic map labelling1 problem. A few days ago I mentioned that this problem is (i) a lot harder than it first appears and (ii) a wonderful interview problem. I still think it's a good interview question! The easy case, where the items are spread out enough that they don't conflict, tests something fundamental and elementary, but nontrivial (can you store data appropriately, accept input accurately, and construct something that depends on both?). The general case is not at all simple, and getting it right requires a range of important skills. There are many more details and sub-problems than one could discuss in an hour, yet the question isn't a black check that allows the candidate to discuss just anything. I'd like to be able to pass my own interviews, so here are some notes on the question. For reference, here's the case2 (with Detroit on the East Coast, Green Bay an arm of Lake Winnipeg, and…