Everything you asked about is rather brainless and simple to do. I can only assume you're asking this because you don't actually know what NorthStar is.
NorthStar projects a bunch of unique constellations on the ceiling from a projector. The robot has a camera that stares straight up up at the ceiling and uses that information to know it's absolute position at all times. But as you can imagine this won't work too well on wacky ceilings that aren't flat. There's no dead-reckoning whatsoever (no compasses, no odometry, no transit time, no relative motion tracking of any kind). It's even simpler in concept- basically drawing a grid on the floor.
From there it's not very hard to see that if the robot always knows where it is on a blank map, it can move along in any type of motion, randomized or not, and flag the current location as a barrier if sensors detect an obstacle. All it has to do is keep moving around to previously unvisited locations, slowly drawing the obstacles (or more importantly the continuous barriers forming the edge of the room) until it has visited every area in within the continuous outer barrier at least once.