text:
The Ramble	42 comments film, popculturevulture
Breaking The Lemniscate: The Ending Of Inception
Man, Inception.
I can't stop noodling it.
Now, to be clear, HERE THERE BE SPOILERS.
Like, for real.
Really real.
Like, we're gonna spoil the whole goddamn ending of the movie.
You had your chance.
I had reservations about the ending to Inception. The ending, as you know if you watched the movie, loosely appears to show a world where Cobb's plan was successful (after much agita and complication), and where he is once more allowed back into the country and back home and finally allowed to be with his children. We think, okay, is this a happy ending, or is it something else? And then Cobb puts his totem — the spinning top — down on the table and it spins and spins and spins and and we hear "Don't Stop Believin'" by Journey playing and then, and then, and then —
Credits.
And maybe I'm mixing this up with the Sopranos a little. Shut up. It's an apt comparison.
The reservations for me orbit the notion of storyteller ambiguity. That level of ambiguity is interesting because it gets people talking, but as a storyteller I don't have a lot of respect for it. You're telling me a story, so tell it. Don't wuss out. Put your balls on the table. A story's ending is everything, and by failing to commit to an ending — and further by failing to commit in a big way, given that the ending of Inception allows for the dramatic pendulum swing that crosses realities and perceptions — a storyteller is more or less giving a half-hearted shrug. Is the glass half-full or half-empty? You decide, he says, and then takes a nap and fouls his pants.
Inception's ending isn't merely a question of little details that could go either way. That's a functional ambiguity. But here we're left with a huge dichotomy — "It's a dream" or "It's reality" — and it ends up being spectacularly jarring. For me, at least. It feels like a cheat. And shows a lack of confidence.
Except, something nagged at me.
Nolan isn't a storyteller lacking confidence.
Plus, you look back at the Sopranos finale, even though that was wildly ambiguous, Chase still had an ending in mind.
And so it occurred to me: Nolan must have an ending in mind, too. Somewhere in that ending is the answer — a declaration of intent. Films are a visual medium so I thought, okay, look back over the visuals and what do we see? The top is for most people the easiest and most forthright clue, and herein I think Nolan learned something from The Prestige —
The spinning top is an artifact of misdirection.
We're going to focus so much on the top that it's hard to see everything else.
Like a magician, Nolan wants you to focus on this while he performs his trick.
Look past the misdirection…
And then, duh, boom, splurch, there it is —
The kids.
Look past the top and you see the kids, and if you see the kids you see that they're the same age they've been in every dream he was having. They're the same age from his memory. They're wearing the same clothes. They're part of the dream: where before the dream-kids would not turn their heads to see, now their heads have turned. They see their father. His life continues. He may now grow old, and without regret.
He's still in the dream. He's still in Limbo.
Maybe he always was. Or maybe he just didn't come out of it when he met Saito.
I don't yet know. That's the fascinating thing. Finding one answer doesn't put all the other answers in line. Each answer asks two more questions. That's great — this infinite lemniscate ever turning, ever looping back, is like the Escher print that are the dreams within the film (or the film itself), a weirdly recursive story that has thematic ties to The Prestige and Memento. And once more, I think Nolan is a confident storyteller, and I think contained within this film are answers. It's a puzzle, and it challenges us to solve it.
I'd originally thought too that the "it's a dream" ending (i.e. top doesn't fall) means it's also what you would consider to be the "negative" ending — but I don't know that to be the case. We still have a sense of reconciliation: he has put his wife to rest, he can now see the faces of his children, he is moving beyond regret, and (if you believe that the rest of the film is "real") he helps negotiate Fischer's troubled past and offers him a feeling of reconciliation (though that inception is a deception).
I'm more and more fascinated by this.
I need to see it again, I think.
I'm also left to wonder what is the deal with that phrase that's oft-repeated through the film: grow old with no regrets. And Ariadne in Greek myth is not a maze builder, is she? But a maze solver? She helps Theseus through the Cretan maze, right? To defeat the Minotaur? Is she even real? Is she part of Cobb? A segmented piece — he can no longer make mazes, but a part of him still can? Or is she real, a person hired by the grandfather to perform "inception" on Cobb? Is this film a con on him rather than on Fischer?
Holy crap, my head hurts.
But anyway: the ending.
You ask me, it's a dream. I don't know how deep or how long, but it's a dream. The clues are there. Ignore the misdirection of the top. Look to the children for your proof. How to explain it otherwise?
Kids and their faces and clothes aside, if the ending is real, tell me how Codd orchestrated the triple kick he needed to wake up with the others in the plane if we see Fisher and Ariadne kick and Codd still needs to find Saito. That's what I want to know…
Morgan Collins
The top never wobbles in any other dream sequence, from what I can remember. While the kids point is good, there also could be artistic license at play. I am fair
Iy certain it is real, just because it is the easiest way for me to not be cheated by the ending.
@Morgan:
Maybe. But to me, that ending is the cheat — if it's real, then we as the audience are asked to believe something purely out of artistic license. We're asked to believe that the dreamlike warmth of this alarmingly positive ending is true. We're asked to believe that the kids are the same age, wearing the same clothes, are playing on the same spot, and aren't looking at their father in precisely the same way. Odd, too, given that they're supposed to be with their grandmother, who doesn't want them to speak to Cobb in the first place.
The ending is awash in a warm, almost phantasmagoric glow. Nobody says anything. Everybody smiles. It all works out so elegantly.
As for the top: I'll continue to assert I think it's misdirection.
The top's wobble is inconclusive: a wobble but a failure to fall is still telling. We've seen it fall before, and this wasn't that.
Further, one thing that I missed on my first "think-through" –? The top isn't Cobb's totem. It never was. It was always Mal's. Once more, a misdirection: what the top does is irrelevant for Cobb, because it isn't his totem (and I suspect he doesn't even have one).
First, Victoria: The triple kick is death and remembrance in Limbo. The same death Cobb and Mal experienced on the train tracks. A nice murder-suicide. Or maybe a double murder with Saito going first (he's already awake when Cobb wakes up). *thinks* Okayokayokay, so we know that when Cobb and Mal when too deep, and found themselves in Limbo, they knew something wasn't quite right, but they couldn't ever put their finger(s) on it. They woke up on the beach of their own mind, the old (real) world sort of forgotten. They spent fifty-something years together in that shared world of theirs, rebuilding parts of their memories, but never knowing if the world they were in was the same world those memories came from, right? So they didn't want to kill themselves, just in case, but at least Cobb knew some shit was wrong. Mal locked away her only connection to the "real world", with the intent of staying in Limbo forever, and Cobb used that to change her mind (the spinning top in the lock-box), leading her to question the reality of her reality, and leading her to decide to kill herself (probably at his gentle urging). Thus, the train tracks.
So at the end of the movie, Ariadne lets go on the porch and falls to her kick. Cobb takes the gun and shoots himself, flying into Limbo. At this point, it has been an unknowable eternity for Saito, but Saito won't die because he's unsure about his reality, just as Mal was. Cobb shows up, and Saito has the realization about everything, causing Cobb to have the same. *sings* SUI-CIIIIIIIIIIIIIIIIIIIDE!
Chuck: It's only been six or nine months since the incident with Mal at the hotel. He's not any younger during the train scene. He's not aged noticeably, and when he talks to his kids on the phone, they ask when he's coming back, as if it hasn't been long enough for them to realize he won't be returning (though Philipa is having her doubts, so it's been more than a couple months). He refers to what he's on as a business trip. Reminded me of pilots or Army folk. "Father is away at the war." "But when's he coming home?" It's not totally unrealistic that the kids might be wearing the same things. Also, as an unreliable narrator (this is a weird suggestion, so bear with me), maybe because those are the clothes they wear at the end, they inform all of his memories of them, so the clothes match. If I remember correctly, they're wearing the same clothes on the beach when he and Ariadne step out of his memory-elevator for a moment.
Also, the top wobbles. It never once shows any signs of wobbling when he's at the table with Saito, or when he spins it in Mal's vault box. The fact that it is not absolutely perfect in its spin means that this reality is the physical.
Double-also, I was really hoping Cobb would become infected with the same idea he gave to Mal, and the ending would be him killing himself even though he has his life back, because he willing chose to save Saito at the risk of losing himself. Maybe a sweet alter-ending on the DVD?
p.s. Sorry for the no-paragraphs.
@Noah —
No worries, re: paragraphs. 🙂
I don't buy it. We don't know how long it's been, do we? Further, it's awfully bizarre and convenient that the end scene is so cozily portrayed. We're really to believe that the kids are the same age, in the same clothing, in the same position, offering to him redemption from the same conflict?
And by the way, I don't think this is a bad ending. I think that's good: I think it shows that in his dream, he's finally past… well, his past.
But that ending, nope, I don't buy it's the real world. Not anymore. I thought it was when I walked out of the theater, but now I'm not so sure.
Further, I'm more and more arriving at the feeling that a great deal of the film is a dream. Maybe all of it. He's stuck in a wall in Mombasa: a truly nightmarish sequence, enemies everywhere, claustrophobic walls crushing inward, and then — bam! Dream logic, there's Saito, magically saving him.
Re: the wobbling top — just because it wobbles means nothing. We have no confirmation of this as a rule. And as noted, it's not his totem. The top's behavior is almost without meaning.
Again, the top is a misdirection. In my mind, anyway.
@chuck Touche Touche.
July 20, 2010	@ 10:10 AM
Ok, oh bearded one. I've also been thinking about this movie – perhaps too much. I was talking with the hubby about it again last night.
He thinks it was reality at the end.
I don't. I think it *was* all a "dream" – Kobb is still in limbo. Everything you pointed out is also why I think he is in limbo – but the kids – that is what nailed it for me. Same clothes, same ages, same hair – SAME EVERYTHING – except now they turn and look at him. His own subconscious finally ALLOWED him to see them again b/c he had finally worked out his issues with Mal, his own guilt, etc. etc.
And you are right – the way it was filmed or the lighting or something – it seems like it was different. There is no way a director would do that and it not MEAN something – right?
But more than that. Remember the dialogue. Remember how different characters – all throughout the film – say to Kobb THE VERY SAME THINGS THAT MAL SAYS TO HIM during her death scene.
I'm asking you to take a leap of faith – Saito says this to him at least once and I *think* I remember someone else saying that too.
A life filled without regret – again – this is repeated several times to Kobb and from different people
It was like his own mind kept throwing these important phrases at him at different times begging him to DEAL with what had happened with Mal. It was all a dream – it was all happening within his mind.
I think there are more but those are the two that jumped out at me and that stayed with me. I NEED to see this film again. I told hubby last night we will have to buy this dvd when it comes out.
Thanks for this. My head hurts again just thinking about this film but in a good way. 😉
Paul DeLaurentis
I think it's a dream, but I'm going to hold off judgement until I watch the film for a second time…hopefully sometime this week. I need to analyze the details this time.
ktbuffy
I believe it is reality at the end, for a completely out-of-the-movie reason: in the credits, the actors playing the kids in the dream sequence are listed as 3 and 5 years old, and there is a separate listing for the kids at 5 and 7 years old. I may have the ages wrong, but to me, that proves that the ending is real, that the kids have grown up since Cobb's visions of them in the dream.
Also, the top wobbled.
But then, Saito touched the top in Limbo, and Cobb had previously said no one was supposed to touch another person's totem.
Yeah, I don't care. I come down firmly on the side of reality.
July 20, 2010	@ 12:09 PM
I'm still not sold that the "wobbling top" means anything at all. Cobb also said that you couldn't let anyone else touch your totem — and the top isn't his totem.
The kids of two ages — I saw that on IMDB. My feeling is that it's Kids On Beach versus Kids At House. Or, alternately, Kids On Phone (Audio), Kids You See (Visual).
Voice actors are the older kids. The kids you see are the younger kids.
Just my guess.
Even if you assume that they're older, the fact they appear at precisely the proper spot to give precisely the redemption he needs is a little… finicky.
My feelings have essentially become that if the end *is* real, it's too neat. It's a cheat. But Nolan is an elegant craftsman, and one who loves misdirection and playing with the audience, which is why I'm comfortable with the ending being a dream.
And maybe the whole film.
Again, it's very possible that the entire storyline is a con on Cobb — a massive in-dream psychotherapy session, with Ariadne as his guide.
Paul DeLaurentis Jr.
Ok…I lied. I went and trolled the internet for some additional feedback. I stumbled upon this blog which seems to contain some interesting theories.
http://www.cinematical.com/2010/07/19/dissecting-inception-six-interpretations-and-five-plot-holes/#comments
I'm leaning towards one of these scenarios but I'll let you judge for yourself.
David Accampo
My first reaction to the ending was similar to yours; it was a cheat. The filmmaker elects NOT to give us closure, leaving us to decide for ourselves… the lady or the tiger.
But then, as I thought about it, I came to a different conclusion. Not quite your misdirection theory, but something else…
By cutting to black where he did, Nolan doesn't tell us if this is dream or reality. Thus, he leaves the viewer with the SAME UNCERTAINTY that Mal felt upon waking. Is what we saw a dream? Is it reality? It could be either. Nolan has planted an uncertainty in our heads, much the same way that Cobb planted uncertainty into Mal's head. I like this take on it, as it seems to fit the major theme of the film.
Here's my current thoughts.
Firstly, the "meaning" of the ending. I think it means that it doesn't matter. I think it's saying that Cobb has finally learned to let go and embrace the reality he is in (whichever one it is) which is the thing he and his wife both struggled so hard with. So it doesn't matter which reality he committed to, it just matters that he committed.
As to what the ending "means to the story," i'm still divided. I think there's a good chance that the whole film is Cobb lost in a series of dreams. He's the only guy who doesn't have a totem. Okay, he does, but its not his. Its his wifes. Where is his? When did he lose it? Is he drifting through dreams without a compass? Then at the end finding one that he can live with.
The other possibillity is that his wife was right, she managed to escape the dreams and he never did.
Or that the whole film is a long con -which we already knew- but the mark is Cobb, NOT Cillian.
Halsted Larsson
There's also the issue of Michael Caine picking him up at the airport in the U.S. when he clearly lives and works abroad. Not impossible but, again, a little too neat – especially given the father relationship being so important to 'inception,' leading to a possible Cobb-is-the-target scenario.
Ultimately, though, I just don't see that leaving the ending open is NECESSARILY a cop out. It certainly can be and more often than not is, but it can be done artistically too. For example, the ambiguity could be echoing Cobb's own lack of certainty — we never saw what happened in those final moments; does he remember them?
Noah: Problem with you explanation though is that Cobb was already in Limbo with Ariadne, Saito and Fisher. So Ariadne drop kicks Fisher and herself out of limbo to ice world, this leaves Cobb an immense time span to get himself and Saito kicked too. Then Cobb washes up and meets Saito old and shriveled. So… for that to work Cobb must have suicide kicked himself out of limbo to ice world and back into limbo for Saito to have aged so much and Cobb to stay the apparent same age. Okay… possible. Then what ? They simul-suicide kick themselves back into iceworld ? But then there's still hotel world and van world to go to reality. With reality 'happening so much faster' than dream worlds (falling van at 9.81 m/s squared takes, what ? 30 seconds at tops) and even hotel world having only a few minutes to make the kick, I don't see how Cobb's got enough time to kick six times all the way through to reality !
In general: Nice as this discussion of real vs. dream is, I've officially changed my opinion. What happened ? Schrodinger happened ! The cat is both dead and alive !
Rob donoghue
Longer answer later, but just because it's not a dream doesn't mean it's real, and I'm ok with the final spin of the top being on the meta layer.
There are even more reasons it could be a dream, but one missing element keeps me from thinking it is. More on that later.
-rob d
Ok, time for the story logic dance. The top is a bit of sleight of hand. The dreaminess of the conclusion is sleight of hand. The question is not "Is the conclusion a dream?" because that's not important. The question is "Is Cobb the mark?"
If he is the mark, then a lot of stuff cascades from there, and there is a reason for the ending to be a dream, but if he's not, then it's a genuine ending that very artistically leaves in a dangling thread in a movie that has been meticulous in keeping things tidy. Other possibilities (like that he's just hallucinated EVERYTHING and never left limbo) are so narratively unsatisfying that I dismiss them out of hand on the basis that Nolan is not a useless douche.
Now, the idea that the con man is actually the subject of a long con over the course of a movie is not new territory, so that certainly makes it fair game. In addition to the number of sequences (Mumbasa especially) shot in the real world that seem dreamlike (including possible subtle things, like the fact that Michael Caine is where _Cobb_ would envision him – in a classroom – rather than an office) , there are a number of pointers that would be consistent with a con. the two biggest:
1) Cobb's own point about Catharsis being the most powerful route to inception definitely resonates with his own situation. If he's being setup for an inception himself, it could hardly be more perfect.
2) Ariadne's insertion is perfect for a con (and the name is so on the nose as to be hard to ignore). Remove the known quantity, force the mark to bring someone in so he feels like he's the one making the decision so he has no reason to question it. She is both unusually talented and unusually insightful[1]. Perhaps not impossibly so, but certainly in a way that someone who already knows more than their letting on would appear to be.
There are other interesting pointers – the Mister Charles gambit resonates with some real world material – and all in all it's safe to say that if it _is_ a con, all the pieces are in place. Enough pieces, laid out artfully and not particularly hidden, to raise the question.
The problem is, as a con, it goes no farther than that.
On a practical level, if the entirety of real world in the movie was a dream, then the movie violates its own rules about how dreams work (either in terms of how numbers of layers work or in terms of how Limbo works) and while that's possible in the abstract, it would be a horrible cheat. And since Nolan is smart enough to not cheat and, as noted, not a douchebag, I reject that possibility.
But that doesn't mean the resolution, and possibly other parts of seeming real-world events weren't actually dreams. He doesn't always have a chance to test the top, and to be frank, the icon defense only works against people who don't know you. People who can rifle through your pockets while your asleep can get their hands on the thing easily enough[2] and make one in a dream that "feels right"
So, again, the prospect of a con is _possible_, but this is where I hit a wall.
If he's the mark, what's the endgame? What is it that someone is trying to plant (or remove)? It's possible that the endgame is to save him from himself, but if so, that moment of resolution (and catharsis) happened in Limbo when he let his wife go. Returning to see the kids is a nice conclusion to that, and emotionally powerful, but it's not what fixes him. So while I would not rule out the prospect of a benevolent scam, that would actually argue against the conclusion being a dream.
But outside of that? I see no endgame. And I've looked pretty hard for one. There's enough evidence of how a caper could be pulled that I'm willing to believe the conclusion is a dream if someone can present a compelling argument for what con is being pulled. That one piece, and I'll totally flip. But i don't see it.
Otherwise, Nolan's totally playing with us – a bit of uncertainty was the best possible way to end it since it's only as uncertain as you want it to be, and it's uncertain in a way that upholds the theme nicely.[3]
Plus, clocking in at 3 hours of intensely tight construction with a magnificently sustained climax, a brief coda of a happy ending is hardly a cop out. It's a summer movie, after all.
-Rob D.
1 – Minor aside on this. Arthur totally knows the problem and how bad it is. But he lets it slide. He's that guy. Leo's performance was fantastic, but Levitt's Arthur really nailed it for me.
2 – And, notably, we know what every character except for Saito's icon is, and Saito probably shouldn't have one. Though it is curious that he recognizes Cobb's.
3 – Oh, and one more bit of nerdbait. You know what would make the top rattle like that (because, no, dream top is not uncertain)? The dream shaking as the dreamer notices an incongruity. Like the age of the children! Da-Da-DUUUUUM!
Pure theory here, but it hung together for me.
Limbo gets a bit of a pass because it's laid down pretty clearly that the rules there are different. Nothing, for example, demands that time passes at the same rate for Saito and Cobb, and, in fact, I'd posit that it probably doesn't, at least in part because of the structural nature of Limbo.
Notice that in each layer of a dream, one person couldn't go any deeper – the person whose dream it was. Limbo seems to violate that rule as it's an unformed space. Note that if all Cobb needed to do was to get to limbo, he could have shot himself in the head, but since they needed to get Fisher out (explicitly, because they needed to get Fisher out in a VERY SPECIFIC ORDER) they needed to go down procedurally, so Fisher could be drawn back up procedurally.
So, given that Limbo is unformed dreamspace, it is likely that it is personal (albeit connected, if the dreamers are connected) rather than architected in the head of an external dreamer. Now, maybe Cobb and Ariadne really went to limbo, but it's equally possible that they just got very close. Ariadne had not architected a fourth level, so it got filled with all the necessary elements from Cobb, so it looked like his Limbo.
Now, the "anteroom to limbo" thing is mostly just splitting hairs, but it does tie up one loose end: If Cobb does not truly go on to limbo until after Ariadne is sent back up and everyone kicks, the Saito went their first, and we don't need different timeflows to account for his aging up before Cobb arrives.
All of which comes back to the point that the waking from Limbo is direct, and does not pass through intervening layers (which would be a feature rather than bug, except for the fact that Limbo is dangerous, and killing yourself out of limbo when your body will send you back is probably a bad cycle) . This seems to hold up as it seems everyone else on the plane had been awake, at least for a little while, when Cobb and Saito wake up (and it's at least implied that Cobb and Moll woke directly to reality).
Anyway, that was my impression.
Martin Mulrooney
I disagree that it was a dream, but thanks for an interesting read. Here is my own article about the ending (leaning more towards it being reality) if anyone is interested:
http://alternativemagazineonline.co.uk/2010/07/21/feature-article-spinning-tops-and-unicorns-the-ending-of-inception/
So, thinking about it more, there is one point where, structurally speaking, it would not be a cheat for it all to have been a dream. It is possible that, when Leo wakes up in the first class cabin, about to land in LAX, that is the first time he has woken up in the entire movie. While there are a few looks, there's nothing concretely communicated, and it's possible that he simply populated his dream (about coming home to a family that's lost their mother) with the other people in first class (a la the wizard of oz). Curiously, this means that the topspin actually means nothing (except him carrying forward a bit of dreamlogic) except perhaps that it reveals the true nature of the top – actually spinning like a top rather than spinning forever or falling immediately (which are both, in this logic, false flags). The dreaminess of the conclusion is more _because_ it's real than anything else.
This holds together, but I admit I don't like it. I loved the supporting characters, and am dissatisfied with the idea that they aren't real (so to speak). However, while I reject it personally, I have to concede that it would not be cheating, so it's definitely within bounds.
@Rob:
I'm so sad I haven't gotten to talk this up more with you. Your comments and brain-work are, as always, kick-ass.
Lemme comment a moment about the supporting characters, though —
I'm of a mind where, if the whole film is a dream, I'm very happy with the supporting characters.
If the film is by and large reality, then I'm a bit disappointed in them.
The backup team — excluding Saito — is filled with somewhat flimsy characters. We have little glimpse into their motivation. We have almost zero glimpse into their backstory. We get a feeling of how they act, but mostly it's shallow — "Arthur is cautious, Eams is eager, Ariadne is the therapist, the chemist is… uhhh." But we don't really know why they're that why. Ariadne's rather bold and caution-free exploration of Cobb's psyche is interesting, but not that believable.
But! But, once you start putting them to the test as either projections *or* as part of a con on Cobb himself ("Con on the Cobb?") (Sorry.), then their cipher-like nature actually makes sense. It becomes a feature, not a bug.
Really, the only one I wouldn't want to let go of is Arthur (and to a lesser extent Eames; he was fun – I dig that kind of character) because I really feel like he was all there and all in, in a way that didn't wear it on his sleeve. While the Chemist was one-note, I really feel that Arthur was merely understated – he's that guy that stands by his friend as everything is going to hell, but without making a big deal of it.
But as with all understatement, much rests on the observer. The text as presented definitely holds up with the crew as imaginary, and I could be projecting onto Arthur. So, yeah, I'm still sticking with it being real because that satisfies me, but I can't argue structurally against "Dream on the flight".
I should clarify that I always enjoyed watching the characters — but when I walked away from the theater, I felt ultimately unsatisfied. I couldn't now tell you their motivation, and in a heist movie, motivation is everything. I wrote once (maybe on Do Some Damage) that crime is such a great genre because it's always active, because it always demands something from the character — we must know their motivations. Nobody commits crime in a vacuum. Yes, it can be about money, but it's never *just* about money.
In INCEPTION, it's not even about money. I mean, it technically is, but we never know how much, and nobody seems particularly greedy, and they're all gleefully on-board in this lunatic con.
When I walked away, I felt myself wondering, who are those characters?
I knew Saito well enough. I knew Fischer. Cobb, definitely, and Mal, too.
The others were just… well, to use the chess metaphor, pawns.
I very much enjoyed them, but they felt like roles, not characters. Which, given the possibly dream-like nature, can be a good thing — but if it ends up as reality, I feel they're a bit hollow.
(which is why, in the "Con for his own good scenario" I consider it highly likely that Arthur is both genuinely his friend and probably the client. Fits my sensibilities of Arthur as the friend who will also one day decide to put you in rehab whether you like it or not.)
I pondered the notion that Arthur is the "con-man," but the father(-in-law) is the client.
I think, if it's a non-friendly con, the invader (tourist, natch) is almost certainly Saito, hacking his brain on the flight. But the endgame concern stands.
interesting thoughts there, folks. I like the idea that the ending in first class is the first time we see reality. Interesting.
Peter Sturdee
Well, I just saw this — and have been pondering it, too. A couple of observations:
Near the beginning, Mal (I think), asks Cobb if he's still being chased by an anonymous international corporation, implying that it's a dream thing. The corporation sure sounds like the defenses of a someone trained to resist these dream invasions.
When Cobb is in Mombasa, the agents that are following him quickly multiply in number, and suddenly sprout guns. This also follows the pattern of trained defenses.
Other than the 747, there are no scenes devoted to Cobb traveling in the "real" world, he's just where he needs to be. And, while I admit that scenes depicting people going places are dead pieces of a film, they are a common motif used to segue between locations. Their absence is notable.
When Cobb and Ariadne are in Limbo, and Cobb is showing Ariadne the houses, they walk into a sky scraper as Cobb is telling her about the house he and Mal built in the dream, the one they never owned — the design sensibility of a steel and glass skyscraper, with the house they wanted to live in contained in it (you can have that because it's in a dream). The room where Cobb and Ariadne then meet Mal in Limbo, is the room where Cobb couldn't call to his kids, where Ariadne finds Cobb when she sneaks into his dream, and the room at the final moment of the film.
Cobb and Mal did get trapped in Limbo, and Cobb showed Mal how to get out of it — or, at least, up a layer. Mal (the real one), I believe, realized that she was still in a dream (she left her top on the floor in the hotel room before jumping), so she could have tested for reality with it before she jumped. She tried to convince Cobb to jump, too, but he wouldn't listen to her — even after she stacked the chips in favour of that option. Cobb never had his own token, as @stringer pointed out.
Which makes me think about the legal charges against Cobb; those feel pretty contrived, too. Mal got three psychologists to pronounce her sane and then wrote a letter saying how her husband was planning to kill her. That's not exactly a guaranteed conviction, it would be easy to prove reasonable doubt just by asking why would she go to those lengths to prepare that kind of documentation, why not just go to the police? I think the charges are part of the guilt Cobb is dealing with.
Now, if this is all dream, then the tragedy of the film is that Cobb never had faith enough to wake up. Though, I think the real story is about Cobb forgiving himself from the guilt he's carrying, and that's compelling enough for me.
Besides, the assumption is that we weren't allowed to watch the top long enough for it to fall. What if we did see the top spinning for log enough? Now, the top spinning isn't a really good pass/fail kind of test. We are lead to believe that it will either fall (we're seeing reality), or keep spinning (we're seeing dream). But we don't know how long it will take to fall, so we are never able to conclude, with certainty, if we're seeing a dream. Because of that, I don't think it's a cop-out to conclude, because the top didn't fall, that we are seeing a dream. It only feels like the certainty about that was robbed from us because we weren't allowed to see the top fall — but isn't that the Pollyanna inside of us? The top was spinning for a very long time before the credits rolled.
I'd say it was a dream. I mean, it was meant to be "ambiguous", but since the top doesn't fall and that's not very ambiguous at all, I don't really think it is. How long would we have to watch the top to know for certain it was a dream? I think saying it's ambiguous is a way of the audience pussying out of admitting that they got the Bad Ending.
I haven't read the comments, though, so maybe someone else mentioned this a bit more eloquently already.
… That said, I hadn't really considered that the whole thing could be a dream. Very, very interesting.
I have nothing to add – at least not yet – but wanted to say thanks. This post and a lot of the stuff in the comments (esp Rob D's insight) were EXACTLY what I needed.
Random Thoughts about Inception | Blog of Fate
[…] bad for the main protagonist. Check: assuming you believe Inception has an ending (which I know Chuck Wendig does), it's certainly an ambivalent one at […]
Inception: Planting Ideas – Here Be Spoilers | Geekcentricity
[…] you want to read more thoughts about this film, check out Chuck Wendig's post at Terrible Minds or Cinematical's exhaustive study of the movie. Also, check out this interview with Dileep […]
Darren G Miller
I finally saw Inception. Wow!
My post about it is here: http://geekcentricity.com/2010/07/inception-planting-ideas-here-be-spoilers.html
bark » what's all the fuss about
[…] is trying to tell us. among the more interesting parsers and theory-spinners are the folks at terrible minds and cinematical—and when i say "folks" i absolutely mean to include both the original […]
guiltyx
August 2, 2010	@ 1:24 AM
The sound of a top falling to rest can be heard after the credits have finished.
Pro-tip: never leave until the fat perfectly balanced spinning top sings, I mean stops 🙂
August 2, 2010	@ 10:54 AM
Some really great conversation here. I'd like to pick people's brains a bit on names and the significance thereof.
Ariadne, as Rob notes, is just too on-the-nose to be coincidental (it could be the screenwriters being cute, rather than the in-movie dream designers, but I doubt it, given how deliberate the other aspects of the film are.)
Cobb is a Middle English word for spiders (hence cobwebs). And Cobb certainly spins webs in this film.
The Eameses (Charles and his wife Ray) were rather famous architects and designers, another common theme in the movie, so I suspect this is not a coincidence.
There are two Robert (Bobby?) Fischers, and we see that Ariadne's fetish is a chess piece. Probably some sort of connection there, I'd guess.
That's enough that the rest are probably significant as well, but I'm not quite sure how.
Yusuf: Possibly just for the notion of drugs being linked to Arabism (hashish and opium, which are associated with dreaming)
Arthur: the zero-g fight scene reminded me of some sequences from 2001, which makes me think perhaps this is a nod to Arthur C. Clarke, but that's definitely a stretch.
Saito: nothing comes to mind, but it's so common a Japanese surname that there are lots of options to chose from.
And of course:
Mal: bad…in the latin (as River Tam would say) Probably it's not that straightforward. Short for what, then?
They didn't have the same clothes:
http://www.associatedcontent.com/article/5650734/inception_ending_clue_given_by_costume.html?cat=40
Tori A
October 19, 2010	@ 6:42 PM
My opinion on the end of the movie was that it was more thematic than plot-deciding. The ending was left for the individual viewer to choose because it was left for Cobb to choose.
At a certain point, no one can prove anything to be real. The universe can't be really proven to exist as it seems, or even at all.
So people have to choose their own realities, which is a major theme of the movie. Whether the top fell or not is actually irrelevant to the ending, because the point was that Cobb had chosen his reality and was ready to go home.
This is the whole point of the director, lol
Its to make you guys do THIS kind of talk .. and you guys are doing it 😀
Totally falling for it.
I would just like to point out to you that the children are not the same age at the end. And not just in the movie, but in real life. In all of the dream sequences, Cobb's daughter Phillipa is portrayed by 3-year-old Claire Geare and his son James is portrayed by Christopher Nolan's 20-month-old son Magnus. But at the end of the film, Phillipa is portrayed by Claire Geare's 5-year-old sister Taylor Geare and James is portrayed by their brother, Jonathan Geare.
Soooooooo, not a dream.
Top 20 Terribleminds Posts Of 2010
January 1, 2011	@ 12:03 AM
[…] 17: Breaking The Lemniscate: The Ending Of Inception […]
Speak Your Mind, Word-Nerds	Cancel reply


text:
\section{Introduction}

Given a set of terminals, which are points in $\ensuremath{\mathbb{R}}^d$, the \emph{minimum
  Manhattan network problem} (MMN) asks for a minimum-length
rectilinear network that connects every pair of terminals by a
Manhattan path (\emph{M-path}, for short), that is, a path consisting
of axis-parallel segments whose total length equals the pair's
Manhattan distance.

\begin{wrapfigure}{R}{.36\textwidth}
  \vspace*{-5ex}

  \hspace{1ex}\subfloat[%
  an MMN for $\{a,b,c,d,e,f\}$]%
  {\includegraphics[page=1]{mmn-vs-gmmn}}
  \hfill
  \subfloat[%
  a GMMN for $\{(a,\!b),(c,\!d),(e,\!f)\}$]%
  {\includegraphics[page=2]{mmn-vs-gmmn}}
  \caption{MMN versus GMMN in 2D.}
  \label{fig:mmn-vs-gmmn}
  \vspace*{-3ex}
\end{wrapfigure}
In the \emph{generalized minimum Manhattan network problem} (GMMN), we
are given a set $R$ of $n$ unordered terminal \emph{pairs}, and the
goal is to find a minimum-length rectilinear network such that every
pair in~$R$ is \emph{M-connected}, that is, connected by an M-path.
GMMN is a generalization of MMN since $R$ may contain all possible
pairs of terminals.  Figure~\ref{fig:mmn-vs-gmmn} depicts examples of
both network types.

We remark that in this paper we define $n$ to be the number of
terminal \emph{pairs} of a GMMN instance, whereas previous works on
MMN defined~$n$ to be the number of \emph{terminals}.

Two-dimensional MMN (2D-MMN) naturally arises in VLSI circuit layout
\cite{gln-ammn-01}, where a set of terminals (such as gates or
transistors) needs to be interconnected by rectilinear paths (wires).
Minimizing the cost of the network (which means minimizing the
total wire length) is desirable in terms of energy
consumption and signal interference. The additional requirement that
the terminal pairs are connected by \emph{shortest} rectilinear paths
aims at decreasing the interconnection delay (see Cong et
al.~\cite{clz-pdid-93} for a discussion in the context of rectilinear
Steiner arborescences, which have the same additional requirement; see
definition below).  Manhattan networks also arise in the area of
geometric spanner networks. Specifically, a minimum Manhattan network
can be thought of as the cheapest spanner under the $L_1$-norm for
given a set of points (allowing Steiner points). Spanners, in turn,
have numerous applications in network design, distributed algorithms,
and approximation algorithms.

MMN requires a Manhattan path between every terminal pair.  This
assumption is, however, not always reasonable.  Specifically in VLSI
design a wire connection is necessary only for a, often comparatively
small, subset of terminal pairs, which may allow for substantially
cheaper circuit layouts.  In this scenario, GMMN appears to be a more
realistic model than MMN.

\paragraph{Previous Work.}

MMN was introduced by Gudmundsson et al.~\cite{gln-ammn-01} who
gave 4- and 8-approximation algorithms for 2D-MMN
running in $O(n^3)$ and $O(n \log n)$ time, respectively.
The currently best known approximation algorithms for 2D-MMN have
ratio~2; they were obtained independently by Chepoi et
al.~\cite{cnv-raamm-08} using an LP-based method, by
Nouioua~\cite{n-eprmc-05} using a primal-dual scheme, and by Guo et
al.~\cite{gsz-gc2am-11} using a greedy approach.  The complexity of
2D-MMN was settled only recently by Chin et al.~\cite{cgs-mmnnp-11};
they proved the problem NP-hard.  It is not known whether 2D-MMN is
APX-hard.

Less is known about MMN in dimensions greater than 2. Mu{\~n}oz et
al.~\cite{msu-mmnp3-09} proved that 3D-MMN is NP-hard to approximate
within a factor of 1.00002.  They also gave a constant-factor
approximation algorithm for a, rather restricted, special case
of 3D-MMN.  More recently, Das et al. described the first
approximation algorithm for MMN in arbitrary, fixed dimension with a
ratio of~$O(n^\ensuremath{\varepsilon}\xspace)$ for any $\ensuremath{\varepsilon}\xspace > 0$ \cite{dgkksw-ammnh-11}.

GMMN was defined by Chepoi et al.~\cite{cnv-raamm-08} who asked
whether 2D-GMMN admits an $O(1)$-approximation. %
Apart from the formulation of this open problem, only special cases of
GMMN (such as MMN) have been considered %
so far.

One such special case (other than MMN) that has received significant
attention in the past is the \emph{rectilinear Steiner arborescence
  problem} (RSA).  Here, we are given $n$ terminals lying in the first
quadrant and the goal is to find a minimum-length rectilinear network
that M-connects every terminal to the origin~$o$.
Hence, RSA is the special case of GMMN where~$o$ is
considered a (new) terminal and %
the set of terminal pairs
contains, for each terminal $t \ne o$, only the pair~$(o,t)$.  RSA was
introduced by Nastansky et al.~\cite{nss-cmtda-74} and has mainly been
studied in~2D.
2D-RSA is NP-hard~\cite{ss-rsapn-00}.
Rao et al.~\cite{rshs-rsap-92} gave a 2-approximation algorithm for
2D-RSA.  They also provided a conceptually simpler $O(\log
n)$-approximation algorithm based on rectilinear Steiner trees.  That
algorithm generalizes quite easily to dimensions $d > 2$ (as we show
in the appendix).
Lu et al.~\cite{lr-ptasrsap-00} and, independently,
Zachariasen~\cite{z-arsap-00} described polynomial-time approximation
schemes (PTAS) for RSA, both based on Arora's technique~\cite{a-asnph-03}.
Zachariasen pointed out that his PTAS can be generalized to the
all-quadrant version of RSA but that it seems difficult to extend the
approach to higher dimensions.

\paragraph{Our Contribution.}

Our main result is an $O(\log^{d+1} n)$-approximation algorithm for
GMMN (and, hence, MMN) in $d$ dimensions.
For the sake of simplicity, we first present our approach in 2D (see
Section~\ref{sec:polyl-appr-two}) and
then show how it can be generalized to higher dimensions (see
Section~\ref{sec:gener-high-dimens}).  We also provide an improved and
technically more involved $O(\log n)$-appro\-ximation for the special
case of 2D-GMMN, but this approach does not seem to generalize to
higher dimensions; see Section~\ref{sec:impr-algor-two}.
To the best of our knowledge, we present the first approximation
algorithms for GMMN.  Our result for 2D is not quite the
constant-factor approximation that Chepoi et al.\ were asking for, but
it is a considerable step into that direction.  Note that the
poly-logarithmic ratio of our algorithm for GMMN in $d \ge 3$
dimensions constitutes an exponential improvement upon the previously
only known approximation algorithm, which solves the special case
MMN, with a ratio of $O(n^\ensuremath{\varepsilon}\xspace)$ for any $\ensuremath{\varepsilon}\xspace>0$
\cite{dgkksw-ammnh-11}.

Our algorithm for GMMN is based on divide and conquer.  We identify
each terminal pair with its $d$-dimensional bounding box.
Consequently, we consider~$R$ a set of $d$-dimensional boxes.  We use
$(d-1)$-dimensional hyperplanes to partition~$R$ recursively into
sub-instances.  The base case of our partition scheme consists of GMMN
instances where all boxes contain a common point.  We solve the
resulting special case of GMMN by reducing it to RSA.  We have
postponed the running-time analysis to Appendix~\ref{sec:runningtime}.

\section{Polylogarithmic Approximation for Two Dimensions}
\label{sec:polyl-appr-two}

In this section, we present an $O(\log^2n)$-approximation algorithm
for 2D-GMMN.  The algorithm consists of a \emph{main algorithm} that
recursively subdivides the input instance into instances of so-called
\emph{$x$-separated} GMMN; see Section~\ref{sec:main-algorithm}.  We
prove that the instances of $x$-separated GMMN can be solved
independently by paying a factor of $O(\log n)$ in the approximation
ratio.  Then we show how to approximate $x$-separated GMMN within
ratio $O(\log n)$; see Section~\ref{sec:appr-x-separ}.  This yields an
overall ratio of $O(\log^2n)$.

\subsection{Main Algorithm}
\label{sec:main-algorithm}

Our approximation algorithm is based on divide and conquer.  Let $R$
be the set of terminal pairs that are to be M-connected.  We identify
each terminal pair with its bounding box, that is, the smallest
axis-aligned rectangle that contains both terminals.  As a consequence
of this, we consider $R$ a set of rectangles.  Let $\ensuremath{m_{x}}\xspace$ be the
median in the multiset of the $x$-coordinates of terminals.  We
identify $\ensuremath{m_{x}}\xspace$ with the vertical line at $x=\ensuremath{m_{x}}\xspace$.

Our algorithm divides $R$ into three subsets $\ensuremath{R_\mathrm{left}}\xspace,\ensuremath{R_\mathrm{mid}}\xspace$, and $\ensuremath{R_\mathrm{right}}\xspace$.
The set~$\ensuremath{R_\mathrm{left}}\xspace$ consists
of all rectangles that lie {\em completely} to the left of the
vertical line $\ensuremath{m_{x}}\xspace$.  Similarly, the set $\ensuremath{R_\mathrm{right}}\xspace$ consists of all
rectangle that lie {\em completely} to the right of~$\ensuremath{m_{x}}\xspace$.  The
set $\ensuremath{R_\mathrm{mid}}\xspace$ consists of all rectangles that intersect $\ensuremath{m_{x}}\xspace$.

We consider the sets \ensuremath{R_\mathrm{left}}\xspace, \ensuremath{R_\mathrm{mid}}\xspace, and \ensuremath{R_\mathrm{right}}\xspace as separate instances
of GMMN and apply
our algorithm recursively to~\ensuremath{R_\mathrm{left}}\xspace and to~\ensuremath{R_\mathrm{right}}\xspace.  The union of the two
resulting networks is a rectilinear network that M-connects all
terminal pairs in~$\ensuremath{R_\mathrm{left}}\xspace\cup\ensuremath{R_\mathrm{right}}\xspace$. %

It remains to M-connect the pairs in~\ensuremath{R_\mathrm{mid}}\xspace.  We call an GMMN instance
(such as~\ensuremath{R_\mathrm{mid}}\xspace) \emph{$x$-separated} if there is a vertical line (in our
case $\ensuremath{m_{x}}\xspace$) that intersects every rectangle.  We exploit this property
to design a simple $O(\log n)$-approximation algorithm for
$x$-separated GMMN; see Section~\ref{sec:appr-x-separ}.  Later, in
Section~\ref{sec:impr-algor-two}, we improve upon this and describe an
$O(1)$-approximation algorithm for $x$-separated GMMN.

To analyze the performance of our main algorithm, let $\rho(n)$ denote
the algorithm's worst-case
approximation ratio for instances with $n$ terminal
pairs.  Now assume that our input instance $R$ is a worst case.  More
precisely, the cost of the solution of our algorithm \emph{equals}
$\rho(n)\cdot\opt$, where $\opt$ denotes the cost of an optimum
solution~\ensuremath{N_\mathrm{opt}}\xspace to~$R$.  Let~\ensuremath{N_\mathrm{left}}\xspace and~\ensuremath{N_\mathrm{right}}\xspace be the parts of~\ensuremath{N_\mathrm{opt}}\xspace to the
left and to the right of~\ensuremath{m_{x}}\xspace, respectively.

Due to the choice of $\ensuremath{m_{x}}\xspace$, at most $n$ terminals lie to the left of
$\ensuremath{m_{x}}\xspace$.  Therefore, $\ensuremath{R_\mathrm{left}}\xspace$ contains at most $n/2$ terminal pairs.  Since
$\ensuremath{N_\mathrm{left}}\xspace$ is a feasible solution to $\ensuremath{R_\mathrm{left}}\xspace$, we conclude that the cost of
the solution to $\ensuremath{R_\mathrm{left}}\xspace$ computed by our algorithm is bounded by
$\rho(n/2)\cdot\|\ensuremath{N_\mathrm{left}}\xspace\|$, where $\| \cdot \|$ measures the length of a
network.  Analogously, the cost of the solution
computed for $\ensuremath{R_\mathrm{right}}\xspace$ is bounded by $\rho(n/2)\cdot\|\ensuremath{N_\mathrm{right}}\xspace\|$.  Now we assume that we
can approximate $x$-separated instances with a ratio of
$\rho_x(n)$.  Since $\ensuremath{N_\mathrm{opt}}\xspace$ is also a feasible solution to
the $x$-separated instance $\ensuremath{R_\mathrm{mid}}\xspace$, we can compute a solution of cost
$\rho_x(n)\cdot\opt$ for $\ensuremath{R_\mathrm{mid}}\xspace$.

Therefore, we can bound the total cost of our algorithm's solution $N$ to~$R$ by
\begin{displaymath}
  \rho(n)\cdot\opt=\|N\|\leq \rho(n/2)\cdot(\|\ensuremath{N_\mathrm{left}}\xspace\|+\|\ensuremath{N_\mathrm{right}}\xspace\|)+\rho_x(n)\cdot\opt\,.
\end{displaymath}
Note that this inequality does not necessarily hold if $R$ is \emph{not} a worst case since then $\rho(n)\cdot\opt>\|N\|$.  The networks~$\ensuremath{N_\mathrm{left}}\xspace$ and~$\ensuremath{N_\mathrm{right}}\xspace$ are separated by~$\ensuremath{m_{x}}\xspace$, hence they are
edge disjoint and $\|\ensuremath{N_\mathrm{left}}\xspace\|+\|\ensuremath{N_\mathrm{right}}\xspace\|\leq\opt$.  This yields the
recurrence $\rho(n)\leq \rho(n/2)+\rho_x(n)$, which resolves to
$\rho(n)=\log n \cdot\rho_x(n)$.  Let's summarize this discussion.

\begin{lemma}
  \label{lem:approx-2d}
  If $x$-separated 2D-GMMN admits a $\rho_x(n)$-approximation,
  2D-GMMN admits a $(\rho_x(n)\cdot\log n)$-approximation.
\end{lemma}

Combining this lemma with our $O(\log n)$ approximation algorithm for
$x$-separated instances described below, we obtain the following
intermediate result.

\begin{theorem}
  2D-GMMN admits an $O(\log^2 n)$-approximation.
\end{theorem}

\subsection{Approximating $x$-Separated Instances}
\label{sec:appr-x-separ}

In this section, we describe a simple algorithm for approximating
$x$-separated 2D-GMMN instances with a ratio of $O(\log n)$.  Let~$R$
be our input. %
Since~$R$ is $x$-separated, all rectangles in~$R$ intersect a common
vertical line.  W.l.o.g., this is the $y$-axis.

The algorithm works as follows.  Analogously to the main algorithm
presented in Section~\ref{sec:main-algorithm}, we recursively
subdivide the $x$-separated input instance, but this time according to
the \emph{$y$-coordinate}. %
As a result of this, the input instance
$R$ is decomposed into \emph{$y$-separated} sub-instances. Moreover,
since each of these sub-instances is (as a subset of $R$) already
$x$-separated, we call these instances \emph{$xy$-separated}.  In
Section~\ref{sec:appr-xy-separ}, we give a specialized algorithm for
$xy$-separated instances. %

Let $\rho_x(n)$ be the ratio of our algorithm for approximating
$x$-separated GMMN instances and let $\rho_{xy}(n)$ be the ratio of
our algorithm for approximating $xy$-separated GMMN instances.  In
Section~\ref{sec:appr-xy-separ}, we show that $\rho_{xy}(n)=O(1)$.
Then Lemma~\ref{lem:approx-2d} (by exchanging $x$- and
$y$-coordinates) implies that $\rho_x(n)=\log
n\cdot\rho_{xy}(n)=O(\log n)$.

\begin{lemma}
  $x$-separated 2D-GMMN admits an $O(\log n)$-approximation.
\end{lemma}

\subsection{Approximating $xy$-Separated Instances}
\label{sec:appr-xy-separ}

It remains to show that $xy$-separated GMMN instances can be
approximated within a constant ratio.  Let $R$ be such an instance.  We
assume, w.l.o.g., that it is the $x$- and the $y$-axis that intersect
all rectangles in~$R$, that is, all rectangles contain the
origin.  Let $\ensuremath{N_\mathrm{opt}}\xspace$ be an optimum solution to $R$.  Let
$N$ be the union of $\ensuremath{N_\mathrm{opt}}\xspace$ with the projections of $\ensuremath{N_\mathrm{opt}}\xspace$ to the $x$-axis
and to the $y$-axis.  The total length of~$N$ is
$\|N\|\leq2\cdot\opt=O(\opt)$ since every line segment of~\ensuremath{N_\mathrm{opt}}\xspace is
projected either to the $x$-axis or to the $y$-axis but not to both.  The
crucial fact about $N$ is that this network contains, for every
terminal $t$ in $R$, an M-path from~$t$ to the \emph{origin}~$o$.
In other words, $N$ is a feasible solution to the RSA instance of
M-connecting every terminal in~$R$ to~$o$.

\begin{wrapfigure}{r}{25ex}
  \includegraphics{rsa+gmmn}
  \caption{Network~$N$ connects all terminals to origin~$o$.}
  \label{fig:rsa+gmmn}
  \vspace*{-3ex}
\end{wrapfigure}
To see this, consider an arbitrary terminal pair $(t,t')\in R$.  Let
$\Pi$ be an M-path connecting~$t$ and~$t'$ in \ensuremath{N_\mathrm{opt}}\xspace; see
Fig.~\ref{fig:rsa+gmmn}.  Note that, since
the bounding box of $(t,t')$ contains~$o$, $\Pi$ intersects both $x$-
and $y$-axis.  To obtain an M-path from~$t$ to~$o$, we follow~$\Pi$
from $t$ to $t'$ until~$\Pi$ crosses one of the axes.  From that point
on, we follow the \emph{projection} of~$\Pi$ on this axis.  We
reach~$o$ when~$\Pi$ crosses the other axis; see the dotted path in
Fig.~\ref{fig:rsa+gmmn}.  Analogously, %
we obtain an M-path from~$t'$ to~$o$.

Let $T$ be the set of terminals in $R$.  We have shown above that
there is a feasible solution $N$ of cost $O(\opt)$ to the RSA instance
with terminal set~$T$.  There is a PTAS for RSA in two dimensions
\cite{z-arsap-00,lr-ptasrsap-00}.  Using this PTAS, we can efficiently
\emph{compute} a feasible RSA solution $N'$ for $T$ of cost
$O(1)\cdot\|N\|=O(\opt)$.  Moreover, $N'$ is also a feasible solution
to the GMMN instance~$R$.  To see this, note that~$N'$ contains, for
every terminal pair $(t,t') \in R$, an M-path~$\pi$ from $t$ to~$o$
and an M-path $\pi'$ from~$o$ to~$t'$.  Concatenating~$\pi$ and~$\pi'$
yields an M-path from~$t$ to~$t'$ as the bounding box of~$(t,t')$
contains~$o$. %
Thus we obtain the following result.

\begin{lemma}
  $xy$-separated 2D-GMMN admits a constant-factor approximation.
\end{lemma}

\section{Generalization to Higher Dimensions}
\label{sec:gener-high-dimens}

In this section, we describe an $O(\log^{d+1}n)$-approximation
algorithm for GMMN in $d$ dimensions, which is a
generalization of the algorithm for two dimensions presented in
Section~\ref{sec:polyl-appr-two}.  Let us view this algorithm from the
following perspective.  In Section~\ref{sec:main-algorithm}, we
reduced GMMN to solving $x$-separated sub-instances at the expense of a
$(\log n)$-factor in the approximation ratio (see
Lemma~\ref{lem:approx-2d}).  Applying the same lemma to the
$y$-coordinates in Section~\ref{sec:appr-x-separ}, we further reduced
the problem to solving $xy$-separated sub-instances, that is, to
instances that were separated with respect to both dimensions.  This
caused the second $(\log n)$-factor in our approximation ratio.
Finally, we were able to approximate these completely separated
sub-instances within constant ratio by solving a related RSA problem
(see Section~\ref{sec:appr-xy-separ}).

These ideas generalize to higher dimensions.  An instance $R$ of
$d$-dimensional GMMN is called \emph{$j$-separated} for some $j\leq d$
if there exist values $s_1,\dots,s_j$ such that, for each terminal pair
$(t,t')\in R$ and for each dimension $i\leq j$, we have that $s_i$
\emph{separates} the $i$-th coordinates $x_i(t)$ of $t$ and
$x_i(t')$ of $t'$ (meaning that either $x_i(t)\leq s_i\leq x_i(t')$ or
$x_i(t')\leq s_i\leq x_i(t)$).  Under this terminology, an
arbitrary instance of $d$-dimensional GMMN is always \emph{0-separated}.

We first show that if we can approximate $j$-separated GMMN with ratio
$\rho_j(n)$ then we can approximate $(j-1)$-separated GMMN with
ratio $\rho_j(n)\cdot\log n$; see Section~\ref{sec:separation}.  Then
we show that $d$-separated GMMN can be approximated within a factor
$\rho_d(n)=O(\log n)$; see Section~\ref{sec:appr-d-sep}.  Combining
these two facts and applying
them inductively to arbitrary (that is, 0-separated) GMMN instances
yields the following central result of our paper.

\begin{theorem}
  \label{thm:gener-high-dimens}
  GMMN in $d$ dimensions admits an $O(\log^{d+1}n)$-approximation.
\end{theorem}

As a byproduct of this algorithm, we obtain an
$O(\log^{d+1}n)$-approximation algorithm for \emph{MMN} where $n$
denotes the number of \emph{terminals}.  This holds since any MMN
instance with $n$ terminals can be considered an instance of GMMN
with $O(n^2)$ terminal pairs.

\begin{corollary}
  \label{cor:mmn}
  \sloppy
  MMN in $d$ dimensions admits an $O(\log^{d+1} n)$-approximation,
  where $n$ denotes the number of terminals.
\end{corollary}

\subsection{Separation}
\label{sec:separation}

In this section, we show that if we can approximate $j$-separated GMMN
instances with ratio $\rho_j(n)$, we can approximate $(j-1)$-separated
instances with ratio $\log n\cdot\rho_j(n)$.  The separation algorithm
and its analysis work analogously to the main algorithm for 2D where
we reduced (approximating) %
2D-GMMN to (approximating) %
$x$-separated 2D-GMMN; see Section~\ref{sec:main-algorithm}

Let $R$ be a set of $(j-1)$-separated terminal pairs.  Let~\ensuremath{m_{x}}\xspace be the
median in the multiset of the $j$-th coordinates of terminals.  We
divide $R$ into three subsets~\ensuremath{R_\mathrm{left}}\xspace, \ensuremath{R_\mathrm{mid}}\xspace, and \ensuremath{R_\mathrm{right}}\xspace.  The set~\ensuremath{R_\mathrm{left}}\xspace consists
of all terminal pairs $(t,t')$ such that $x_j(t),x_j(t')\leq\ensuremath{m_{x}}\xspace$ and
$\ensuremath{R_\mathrm{right}}\xspace$ contains all terminal pairs $(t,t')$ with
$x_j(t),x_j(t')\geq\ensuremath{m_{x}}\xspace$.  The set~$\ensuremath{R_\mathrm{mid}}\xspace$ contains the remaining
terminal pairs, all of which are separated by the hyperplane
$x_j=\ensuremath{m_{x}}\xspace$.  We apply our algorithm recursively to~\ensuremath{R_\mathrm{left}}\xspace and~\ensuremath{R_\mathrm{right}}\xspace.  The
union of the resulting networks is a rectilinear network that
M-connects all terminal pairs $\ensuremath{R_\mathrm{left}}\xspace \cup \ensuremath{R_\mathrm{right}}\xspace$.

In order to M-connect the pairs in $\ensuremath{R_\mathrm{mid}}\xspace$, we apply an approximation
algorithm for $j$-separated GMMN of ratio $\rho_j(n)$.  Note that the
instance $\ensuremath{R_\mathrm{mid}}\xspace$ is in fact $j$-separated by construction.  The analysis
of the resulting algorithm for $(j-1)$-separated GMMN is analogous to
the 2D-case (see Section~\ref{sec:main-algorithm}) and is therefore
omitted.

\begin{theorem}
  Let $1\leq j\leq d$.  If $j$-separated GMMN admits a
  $\rho_j(n)$-approxi\-ma\-tion, then $(j-1)$-separated GMMN admits a
  $(\rho_j(n)\cdot\log n)$-approximation.
\end{theorem}

\subsection{Approximating $d$-Separated Instances}
\label{sec:appr-d-sep}

In this section, we show that we can approximate instances of
$d$-separated GMMN within a ratio of $O(\log n)$ by reducing the
problem to RSA.
Let $R$ be a $d$-separated instance and let $T$ be the set of all terminals in
$R$. %
As $R$ is $d$-separated,
all bounding boxes defined by terminal pairs in $R$ contain a common
point, which is, w.l.o.g., the origin.

As in the two-dimensional case (see Section~\ref{sec:appr-xy-separ}),
we M-connect all terminals to the origin by solving an RSA instance
with terminal set $T$. This yields a feasible GMMN solution to~$R$ since for each pair
$(t,t') \in R$ there is an M-path from $t$ to the origin and an M-path from the origin to $t'$.  The union of these paths is an M-path from $t$ to $t'$ since the origin is contained in the bounding box of $(t,t')$.

 Rao et al.~\cite{rshs-rsap-92} presented an
$O(\log |T|)$-approximation algorithm for 2D-RSA, which
generalizes, in a straight-forward manner, to $d$-dimensional RSA;
see Appendix~\ref{sec:gen-rsa} for details.
Hence, we can use the algorithm of Rao et al.\ to efficiently compute
a feasible GMMN solution.  The following lemma shows that this
solution is in fact an $O(\log n)$-approximation.
The proof is similar to the proof of Lemma~7 in the paper of Das et
al.\ \cite{dgkksw-ammnh-11}.

\begin{lemma}
  \label{lem:lgn-approx-gmmn}
  $d$-separated GMMN admits an $O(\log n)$-approximation for any fixed
  number~$d$ of dimensions.
\end{lemma}
\begin{pf}
  Below we show that there is a solution of cost $O(\opt)$ to the RSA
  instance connecting $T$ to the origin.  Observing that $|T|\leq 2n$
  and using our extension of the $O(\log |T|)$-approximation algorithm
  of Rao et al.\ (see
  Appendix~\ref{sec:gen-rsa}), we can efficiently compute a
  feasible GMMN solution of cost $O(\opt \cdot \log n)$.

We now show that there is an RSA solution of cost $O(\opt)$.  Let $\ensuremath{N_\mathrm{opt}}\xspace$ be an optimal GMMN solution to $R$ and let
$N$ be the projection of $\ensuremath{N_\mathrm{opt}}\xspace$ onto all subspaces that are spanned by some subset of the coordinate axes. Since there are $2^d$ such subspaces, which is a constant for fixed $d$, the cost of $N$ is $O(\opt)$.

It remains to show that $N$ M-connects all terminals to the origin,
that is, $N$ is a feasible solution to the RSA instance.
First, note that $\ensuremath{N_\mathrm{opt}}\xspace\subseteq N$ since we project on the $d$-dimensional space, too.  Now consider an arbitrary terminal pair $(t,t')$ in~$R$
and an M-path $\pi$ in $\ensuremath{N_\mathrm{opt}}\xspace$ that M-connects $t$ and $t'$. Starting
at~$t$, we
follow~$\pi$ until we reach the first point~$p_1$ where one of the
coordinates becomes zero.  W.l.o.g., $x_1(p_1)=0$.  Clearly~$\pi$
contains such a point as the bounding box of~$(t,t')$ contains the origin.
We observe that $p_1$ lies in the
subspace spanned by the $d-1$ coordinate axes $x_2,\dots,x_d$.
From $p_1$ on we follow the projection of $\pi$ onto this
subspace until we reach the first point $p_2$ where another coordinate
becomes zero; w.l.o.g., $x_2(p_2)=0$.
Hence, $p_2$ has at least two coordinates that are zero, that is, $p_2$
lies in a subspace spanned by only $d-2$ coordinate axes.
Iteratively, we continue following the projections of~$\pi$ onto
subspaces with a decreasing number of dimensions until every coordinate is
zero, that is, we have reached the origin. An analogous argument shows that
$N$ also contains an M-path from $t'$ to the origin.
\end{pf}

\section{Improved Algorithm for Two Dimensions}
\label{sec:impr-algor-two}

In this section, we show that 2D-GMMN admits an $O(\log
n)$-approximation, which improves upon the $O(\log^2 n)$-result of
Section~\ref{sec:polyl-appr-two}.  To this end, we develop a
$(6+\ensuremath{\varepsilon}\xspace)$-approximation algorithm for $x$-separated 2D-GMMN, for any
$\ensuremath{\varepsilon}\xspace>0$.  While the algorithm is simple, its analysis turns out to be
quite intricate.  In Appendix~\ref{sec:tightness}, we show tightness.
Using Lemma~\ref{lem:approx-2d}, our new subroutine
for the $x$-separated case yields the following.

\begin{theorem}
  2D-GMMN admits a $((6+\ensuremath{\varepsilon}\xspace)\cdot\log n)$-approximation.
\end{theorem}

Let $R$ be the set of terminal pairs of an $x$-separated instance of
2D-GMMN.  We assume, w.l.o.g., that each terminal pair
$(l,r)\in R$ is separated by the $y$-axis, that is, $x(l) < 0 \le x(r)$.
Let \ensuremath{N_\mathrm{opt}}\xspace be an optimum solution to~$R$.  Let \ensuremath{\opt_\mathrm{ver}}\xspace and \ensuremath{\opt_\mathrm{hor}}\xspace be the
total costs of the vertical and horizontal segments in \ensuremath{N_\mathrm{opt}}\xspace,
respectively.  Hence, $\opt = \ensuremath{\opt_\mathrm{ver}}\xspace+\ensuremath{\opt_\mathrm{hor}}\xspace$.  We first
compute a set~$S$ of horizontal line segments of total cost $O(\ensuremath{\opt_\mathrm{hor}}\xspace)$
such that each rectangle in~$R$ is \emph{stabbed} by some line
segment in~$S$; see Sections~\ref{sec:stabbing-right-part}
and~\ref{sss:both}.  Then we M-connect the terminals to the $y$-axis
so that the resulting network, along with the affected part of the
$y$-axis and the stabbing~$S$, forms a feasible solution to~$R$ of cost
$O(\opt)$; see Section~\ref{sec:algorithm}.

\subsection{Stabbing the Right Part}
\label{sec:stabbing-right-part}

We say that a horizontal line segment~$h$ {\em stabs} an axis-aligned
rectangle~$r$ if $h$ intersects the boundary of~$r$ twice.  A set %
of horizontal line segments is a \emph{stabbing} of a set of
axis-aligned rectangles if each rectangle is stabbed by some line
segment. %
For any geometric object, let its \emph{right part} be its
intersection with the closed half plane to the right of the $y$-axis.
For a \emph{set} of objects, let its right part be the set of the
right parts of the objects.
Let~\ensuremath{R^\mathrm{+}}\xspace be the right part of~$R$,
let~\ensuremath{N^\mathrm{+}}\xspace be the right part of~\ensuremath{N_\mathrm{opt}}\xspace,
and let~\ensuremath{N^\mathrm{+}_\mathrm{hor}}\xspace be the set of horizontal line segments in~\ensuremath{N^\mathrm{+}}\xspace.
In this section, we show how to construct a stabbing of~\ensuremath{R^\mathrm{+}}\xspace of
cost at most $2\cdot\|\ensuremath{N^\mathrm{+}_\mathrm{hor}}\xspace\|$.

For $x' \ge 0$, let $\ell_{x'}$ be the vertical line at $x=x'$.  Our algorithm
performs a left-to-right sweep starting with~$\ell_0$.  Note that,
for every $x\geq 0$, the intersection of~\ensuremath{R^\mathrm{+}}\xspace with~$\ell_x$ forms a
set $\ensuremath{\mathcal{I}}_x$ of intervals.  The intersection of $\ensuremath{N^\mathrm{+}_\mathrm{hor}}\xspace$ ($\bigcup
\ensuremath{N^\mathrm{+}_\mathrm{hor}}\xspace$ to be precise) with~$\ell_x$
is, at any time, a set of points that constitutes %
a \emph{piercing} for~$\ensuremath{\mathcal{I}}_x$, that is,
every interval in $\ensuremath{\mathcal{I}}_x$ contains a point in $\ell_x\cap
\ensuremath{N^\mathrm{+}_\mathrm{hor}}\xspace$.  Note that $\|\ensuremath{N^\mathrm{+}_\mathrm{hor}}\xspace\|=\int |\ell_x\cap \ensuremath{N^\mathrm{+}_\mathrm{hor}}\xspace|dx$.

We imagine that we continuously move~$\ell_x$ from $x=0$ to the right.
At any time, we maintain an inclusion-wise minimal piercing~$P_x$
of~$\ensuremath{\mathcal{I}}_x$.  With increasing~$x$, we only \emph{remove} points
from~$P_x$; we never add points.  This ensures that the traces of the
points in~$P_x$ form horizontal line segments that all touch the
$y$-axis.  These line segments form our stabbing of~\ensuremath{R^\mathrm{+}}\xspace.

The algorithm proceeds as follows.  It starts at $x:=0$ with an
arbitrary minimal piercing~$P_0$ of~$\ensuremath{\mathcal{I}}_0$.  Note that we can even
compute an optimum piercing~$P_0$.  We must adapt~$P_x$
whenever~$\ensuremath{\mathcal{I}}_x$ changes.  With increasing~$x$, $\ensuremath{\mathcal{I}}_x$ decreases
inclusion-wise since all rectangles in~\ensuremath{R^\mathrm{+}}\xspace touch the $y$-axis.  So
it suffices to adapt the piercing~$P_x$ at \emph{event points}; $x$ is
an event point if and only %
if $x$ is the $x$-coordinate of a right edge of a rectangle in~$R^+$.

Let $x'$ and $x''$ be consecutive event points.  Let $x$ be such that
$x' < x \le x''$.  Note that $P_{x'}$ is a piercing for~$\ensuremath{\mathcal{I}}_x$ since
$\ensuremath{\mathcal{I}}_x \subset \ensuremath{\mathcal{I}}_{x'}$.  The piercing~$P_{x'}$ is, however, not
necessarily \emph{minimal} w.r.t.~$\ensuremath{\mathcal{I}}_x$.  When the sweep line
passes~$x'$, we therefore have to drop some of the points in~$P_{x'}$
in order to obtain a new minimal piercing.  This can be done by
iteratively removing points from~$P_{x'}$ such that the resulting set
still pierces~$\ensuremath{\mathcal{I}}_x$.  We stop at the last event point
(afterwards, $\ensuremath{\mathcal{I}}_x=\emptyset$) and output the traces of the piercing.

It is clear that the algorithm produces a stabbing of~\ensuremath{R^\mathrm{+}}\xspace; see the
thick solid line segments in Fig.~\ref{sfg:stabbing-both}.  The
following lemma is crucial to prove the overall cost of the stabbing.

\begin{lemma}
  For any $x\geq 0$, it holds that $|P_x|\leq 2\cdot |\ell_x\cap \ensuremath{N^\mathrm{+}_\mathrm{hor}}\xspace|$.
\end{lemma}

\begin{pf}
  Since $P_x$ is a minimal piercing, there exists, for every $p\in
  P_x$, a \emph{witness interval} $I_p\in \ensuremath{\mathcal{I}}_x$ that is pierced by $p$
  but not by $P_x \setminus \{p\}$.  Otherwise we could remove~$p$
  from~$P_x$, contradicting the minimality of~$P_x$.

  %
  %
  %
  %
  %
  %
  %
  %
  %

  Now we show that an arbitrary point~$q$ on~$\ell_x$ is contained in the
  witness intervals of at most two points in~$P_x$.  Assume, for the
  sake of contradiction, that~$q$ is contained in the witness
  intervals of points $p, p', p'' \in P_x$ with strictly increasing
  $y$-coordinates.  Suppose that~$q$ lies above~$p'$.  But then the
  witness interval~$I_p$ of~$p$, which contains~$p$ and~$q$, must
  also contain~$p'$, contradicting the definition of~$I_p$.  The
  case~$q$ below~$p'$ is symmetric.

  Recall that $\ell_x\cap \ensuremath{N^\mathrm{+}_\mathrm{hor}}\xspace$ is a piercing of $\ensuremath{\mathcal{I}}_x$ and, hence,
  of the $|P_x|$ many witness intervals.  Since every point in
  $\ell_x\cap \ensuremath{N^\mathrm{+}_\mathrm{hor}}\xspace$ pierces at most two witness intervals, the
  lemma follows.
\end{pf}

Observe that the cost of the stabbing is $\int |P_x|dx$.  By the above
lemma, the cost of the stabbing can be bounded by
$\int |P_x|dx \leq \int 2 \cdot |\ell_x \cap \ensuremath{N^\mathrm{+}_\mathrm{hor}}\xspace| dx =
2\cdot \|\ensuremath{N^\mathrm{+}_\mathrm{hor}}\xspace\|$, which proves the following lemma.

\begin{lemma}
  \label{lem:stabhalf}\sloppy
  Given a set~$R$ of rectangles intersecting the $y$-axis, we can
  compute a set of horizontal line segments of cost at most
  \mbox{$2\cdot\ensuremath{\opt_\mathrm{hor}}\xspace$} that stabs~\ensuremath{R^\mathrm{+}}\xspace. %
\end{lemma}

\begin{figure}[tb]
  %
  \subfloat[$S^+$ stabs~$R^+$, and $S$ stabs~$R$.\label{sfg:stabbing-both}]%
  {\includegraphics{stabbing-both}}
  \hfill
  \subfloat[$N=\ensuremath{A_\mathrm{up}}\xspace \cup \ensuremath{A_\mathrm{down}}\xspace \cup S$ is feasible
  for~$R$.\label{sfg:nisfeasible}]%
  {\includegraphics{nisfeasible}}
  \hfill
  %
  %
  \subfloat[$\ensuremath{N_\mathrm{opt}}\xspace \cup \{I\}$ is feasible for RSA instances
  $(L,\ensuremath{\mathrm{top}(I)}\xspace)$, $(H,\ensuremath{\mathrm{bot}(I)}\xspace)$.\label{sfg:i+noptisrsa}]%
  {\hspace{8.8ex}\includegraphics{i+noptisrsa}\hspace{8.8ex}}
  \caption{The improved algorithm for $x$-separated 2D-GMMN.}
    %
    %
    %
    %
    %
    %
    %
  \label{fig:x-separated}
\end{figure}

\subsection{Stabbing Both Parts}
\label{sss:both}

We now detail how we construct a stabbing of~$R$.  To this end we apply
Lemma~\ref{lem:stabhalf} to
compute a stabbing~\ensuremath{S^\mathrm{-}}\xspace of cost at most $2\cdot\|\ensuremath{N^\mathrm{-}_\mathrm{hor}}\xspace\|$ for the
left part~\ensuremath{R^\mathrm{-}}\xspace of~$R$ and a stabbing~\ensuremath{S^\mathrm{+}}\xspace of cost at most $2\cdot
\|\ensuremath{N^\mathrm{+}_\mathrm{hor}}\xspace\|$ for the right part~\ensuremath{R^\mathrm{+}}\xspace.  Note that $\ensuremath{S^\mathrm{-}}\xspace \cup
\ensuremath{S^\mathrm{+}}\xspace$ is not necessarily a stabbing for~$R$ since there can be
rectangles that are not \emph{completely} stabbed by one segment.  To
overcome this difficulty, we mirror~\ensuremath{S^\mathrm{-}}\xspace and \ensuremath{S^\mathrm{+}}\xspace to the
respective other side of the $y$-axis; see
Fig.~\ref{sfg:stabbing-both}.  The total cost of the
resulting set~$S$ of horizontal line segments is at most
$4(\|\ensuremath{N^\mathrm{-}_\mathrm{hor}}\xspace\|+\|\ensuremath{N^\mathrm{+}_\mathrm{hor}}\xspace\|) = 4\cdot\ensuremath{\opt_\mathrm{hor}}\xspace$.  The set~$S$
stabs~$R$ since, for every rectangle~$r \in R$, the larger among its
two (left and right) parts is stabbed by some segment~$s$
and the smaller part is stabbed by the mirror image~$s'$ of~$s$.  Hence,
$r$ is stabbed by the line segment $s\cup s'$.
Let us summarize.

\begin{lemma}
  \label{lem:stabbing}\sloppy
  Given a set~$R$ of rectangles intersecting the $y$-axis, we can
  compute a set of horizontal line segments of cost at most
  \mbox{$4\cdot\ensuremath{\opt_\mathrm{hor}}\xspace$} that stabs~$R$. %
\end{lemma}

\subsection{Connecting Terminals and Stabbing}
\label{sec:algorithm}

We assume that the union of the rectangles in~$R$ is connected.  Otherwise
we apply our algorithm separately to each subset of~$R$ that induces a
connected component of~$\bigcup R$.
Let $I$ be the line segment that is the intersection of the
$y$-axis with $\bigcup R$.  Let~\ensuremath{\mathrm{top}(I)}\xspace and~\ensuremath{\mathrm{bot}(I)}\xspace be the top and bottom
endpoints of~$I$, respectively.  Let $L$ be the set containing every
terminal~$t$ with $(t,t') \in R$ and $y(t) \le y(t')$.
Symmetrically, let $H$ be the set containing every
terminal~$t$ with $(t,t') \in R$ and $y(t) > y(t')$.
Note that~$L$ and~$H$ are not necessarily disjoint.

Using a PTAS for
RSA~\cite{lr-ptasrsap-00,z-arsap-00}, we compute a near-optimal RSA
network~$\ensuremath{A_\mathrm{up}}\xspace$ connecting the terminals
in~$L$ to~\ensuremath{\mathrm{top}(I)}\xspace and a near-optimal RSA network~$\ensuremath{A_\mathrm{down}}\xspace$ connecting the
terminals in~$H$ to~\ensuremath{\mathrm{bot}(I)}\xspace. Then we return the network $N =
\ensuremath{A_\mathrm{up}}\xspace \cup \ensuremath{A_\mathrm{down}}\xspace \cup S$,
where $S$ is the stabbing computed by the
algorithm in Section~\ref{sss:both}.

We now show that this network is a feasible solution to~$R$.
Let $(l,h) \in R$.  W.l.o.g., $l\in L$ and $h\in H$.  Hence,
$\ensuremath{A_\mathrm{up}}\xspace$ contains a path~$\pi_l$ from~$l$ to~\ensuremath{\mathrm{top}(I)}\xspace, see
Fig.~\ref{sfg:nisfeasible}.  This path starts inside the
rectangle~$(l,h)$ and leaves it through its top edge.  Before
leaving~$(l,h)$, the path intersects a line segment~$s$ in~$S$ that
stabs~$(l,h)$.  This line segment is also intersected by the
path~$\pi_h$ in~$\ensuremath{A_\mathrm{down}}\xspace$ that connects~$h$ to~\ensuremath{\mathrm{bot}(I)}\xspace.
Hence, walking along~$\pi_l$, $s$,
and~$\pi_h$ brings us in a monotone fashion from~$l$ to~$h$.

Now, let us analyze the cost of~$N$.  Clearly, the projection of~\ensuremath{N_\mathrm{opt}}\xspace
onto the $y$-axis yields the line segment~$I$.  Hence, $|I|
\le \ensuremath{\opt_\mathrm{ver}}\xspace$.  Observe that $\ensuremath{N_\mathrm{opt}}\xspace \cup \{I\}$ constitutes a solution
to the RSA instance $(L,\ensuremath{\mathrm{top}(I)}\xspace)$ connecting all terminals in~$L$ to~\ensuremath{\mathrm{top}(I)}\xspace and
to the RSA instance $(H,\ensuremath{\mathrm{bot}(I)}\xspace)$ connecting all terminals in~$H$ to~\ensuremath{\mathrm{bot}(I)}\xspace.
This holds since, for each terminal pair, its M-path~$\pi$ in~\ensuremath{N_\mathrm{opt}}\xspace
crosses the $y$-axis in~$I$; see Fig.~\ref{sfg:i+noptisrsa}.
Since~$\ensuremath{A_\mathrm{up}}\xspace$ and~$\ensuremath{A_\mathrm{down}}\xspace$ are near-optimal solutions to these RSA
instances, we obtain, for any $\ensuremath{\varepsilon}\xspace >0$, that
$\|\ensuremath{A_\mathrm{up}}\xspace\|\leq(1+\ensuremath{\varepsilon}\xspace)\cdot\|\ensuremath{N_\mathrm{opt}}\xspace\cup I\|\leq (1+\ensuremath{\varepsilon}\xspace)\cdot (\opt+\ensuremath{\opt_\mathrm{ver}}\xspace)$
and analogously $\|\ensuremath{A_\mathrm{down}}\xspace\|\leq (1+\ensuremath{\varepsilon}\xspace)\cdot (\opt+\ensuremath{\opt_\mathrm{ver}}\xspace)$.

By Lemma~\ref{lem:stabbing}, we have that $\|S\| \le 4 \cdot \ensuremath{\opt_\mathrm{hor}}\xspace$.
Assuming $\ensuremath{\varepsilon}\xspace \leq 1$, this yields
\begin{align*}
  \|N\| & = \|\ensuremath{A_\mathrm{up}}\xspace\| + \|\ensuremath{A_\mathrm{down}}\xspace\| + \|S\|\\
  & \le (2+2\ensuremath{\varepsilon}\xspace) \cdot (\opt+\ensuremath{\opt_\mathrm{ver}}\xspace) + 4\cdot \ensuremath{\opt_\mathrm{hor}}\xspace\\
  & \le (2+2\ensuremath{\varepsilon}\xspace)\cdot\opt+4\cdot(\ensuremath{\opt_\mathrm{ver}}\xspace+\ensuremath{\opt_\mathrm{hor}}\xspace) \\
  & = (6 + \ensuremath{\varepsilon}\xspace') \cdot \opt
\end{align*}
for $\ensuremath{\varepsilon}\xspace' = \ensuremath{\varepsilon}\xspace/2$, which we can make arbitrarily small by
making~\ensuremath{\varepsilon}\xspace arbitrarily small.  We summarize our result as follows.

\begin{lemma}
  $x$-separated 2D-GMMN admits, for any $\ensuremath{\varepsilon}\xspace>0$, a
  $(6+\ensuremath{\varepsilon}\xspace)$-approximation.
\end{lemma}

\section{Conclusion and Open Problems}

We have presented an $O(\log^{d+1}n)$-approximation algorithm for
$d$-dimensional GMMN, which implies the same ratio for MMN.  Prior to
our work, no approximation algorithm for GMMN was known.  For $d \ge
3$, our result is a significant improvement over the ratio of
$O(n^{\ensuremath{\varepsilon}\xspace})$ of the only approximation algorithm for
$d$-dimensional MMN known so far.

In 2D, there is still quite a large gap between the currently best
approximation ratios for MMN and GMMN.  Whereas we have presented an
$O(\log n)$-approximation algorithm for 2D-GMMN, 2D-MMN admits
2-approximations~\cite{cnv-raamm-08,gsz-gc2am-11,n-eprmc-05}---but is
2D-GMMN really harder to approximate than 2D-MMN?
Indeed, given that GMMN is more general than MMN, it may be possible
to derive stronger non-approximability results for GMMN.  So far, the only
such result is that 3D-MMN cannot be approximated beyond a factor of
1.00002~\cite{msu-mmnp3-09}.

Concerning the positive side, for $d \ge 3$, a constant-factor
approximation for $d$-dimen\-sional RSA would shave off a factor of
$O(\log n)$ from the current ratio for $d$-dimensional GMMN.  This may
be in reach given that 2D-RSA admits even a
PTAS~\cite{lr-ptasrsap-00,z-arsap-00}.  Alternatively, a
constant-factor approximation for $(d-k)$-separated GMMN for some
$k\le d$ would shave off a factor of $O(\log^k n)$ from the current
ratio for $d$-dimensional GMMN.

\section*{Acknowledgments}

We thank Michael Kaufmann for his hospitality and his enthusiasm
during our respective stays in T\"ubingen.  We thank Esther Arkin,
Alon Efrat, and Joe Mitchell for discussions.

\bibliographystyle{alpha}

redpajama_set_name: RedPajamaArXiv


It is a pleasure for me to be in front of you and I must admit I feel privileged being here to talk about one of the saddest part of Congolese history and its connection to Britain in bringing about a solution. I would be as brief as possible and other information would come during the debates afterward.
When I was approached to give this talk, I saw it as an opportunity, which one should not miss.
I think there is no need for me to start at the beginning of colonisation of Congo . We all know about it.
What I thought I should focus today is the link between the struggle of the Congolese and the support of Britain . I mean British people. This is mainly because we are in London .
So that led me to a personal dedication in finding the Denominateur Commun to the problems of Congolese since 1885, which I call The Congo Question .
In his book French Lesson In Africa , Peter Biddlecombe, a British writer, said, � Zaire is Britain 's biggest trading partner in French � speaking Africa, but we don't seem to enjoy the amicable relation Zaire has with so many other countries. Which is doubly odd because if it hadn't been for Zaire , or at least Zaire gold, Britain might not have won the last war . For Belgians lent Zaire gold to the British to enable them, in the dark days when they stood alone, to buy armaments from the States .
In this state of affaire, I would like to explain why I always place Britain at the centre of The Congo Question.
At the end of nineteen century, a young man of European descent was given a job in Congo . What he saw there affected his all being. He wanted to expose what he discovered in Congo of King Leopold II. When he turned his energy into writing, that young man became the person we all know today as the British Novelist Joseph Conrad. He decided to bring what he saw in Congo to a wider audience. The cruelties inflicted to Congolese in the name of production and his own experience in Congo became the basis of his masterpiece the novella Heart of Darkness.
Joseph Conrad, as a thinking person, knew where he should stand.
A t the turn of the century almost one hundred years ago after the rise of Western imperialism in Africa and in the time of the exploitation of the Kingdom of Kongo, nearby kingdoms as well as neighbouring lands, were branded Congo Free State; it became almost as natural seeing a Congolese being brutalized, humiliated or even killed than expecting a hot day in Congo itself, in the name of productivity or industrial capitalism. Maybe the term Free in Congo Free State was a Carta Blanca to those involved in the project as administrators in whatever they did in the name of bringing �Light' into �Darkness', in which we saw the natives being stripped of their human dignity.
The horror of that inhumane treatment of the Congolese in the hands of the Belgians at the time, according to Michela Wrong, in her book In the Footstep of Mr. Kurtz , left approximately ten million Congolese dead ; which is also confirmed by the Congolese journalist, Norbert X Mbu � Mputu in his book Cent ans d' Evangelisation du Mai-Ndombe (Diocese d'Inongo) Par les Pères de Scheut , by the Belgian priest Father Daniel Van Groewheghe in his book Du Sang Sur Les Lianes , and also in other books such as the King Leopold's Ghost by Adam Honchschild.
This may confirm that the exploitation of Congo by King Leopold II was among the biggest and most horrific genocides in the last hundred years.
By writing his novella Heart of Darkness , Joseph Conrad started a consciousness related to The Congo Question. Here in Britain , it became acceptable and fashionable to defend the human right of Congolese. It is beyond the scope of this speech to go on details about all the people who became associated to the cause of Congolese.
The publication of that novella brought about the need to defend the human right of Congolese. And the struggle took a different momentum when people such as E. D. Morel, Sir Roger Casement and William Sheppard joined it. Morel was the one who stood out the most.
E.D. Morel was a British national and a critic of the Belgian government policies in Congo Free State . His discoveries of Leopold II's exploitation came from his insider experience working as a clerk for Elder Demptser, a Liverpool-based shipping line, in Britain . When he found the discrepancies between the report (with regard to amounts of import/export goods) compiled by Congo Free State and his own findings, his conscience was challenged. He then quit his job and devoted his time and energy to express his growing concerns about the treatment of natives in Congo and other part of Africa . He wrote many books and pamphlets that openly accused Leopold's Congo Free State of violating human rights and of slaughter. He also published the picture of Congolese with mutilated hands to give the liberation of Congolese a different twist.
The reaction to those pictures in Britain was overwhelming. It resulted in the formation of a movement known as The Congo Reform Association , which was co-founded by Sir Roger Casement and E.D. Morel himself. Most popular individuals of the time joined the struggled as Mr Morel was clever enough to publish those pictures in his newspapers.
I think it is an example for today's Congolese editors and journalist to follow.
And then Britain became the centre of the Congolese liberation movement. Many great minds of the time joined the struggle. The people such as Mark Twain and Sir Arthur Canon Doyle became a part of it.
My friends, I must assure you that there is power in writing; and many people here in Britain are ready to help the Congolese in the quest for solving The Congo Question.
So for something that started as a small book called Heart of Darkness and later on created such support from the British in the cause of the Congolese, there should be a need in coping it. And I can assure you that although dormant; the Congolese still have their vital support within the British people.
For some reason Joseph Conrad's Heart of Darkness is unknown by le commun de mortel in Congo today. And I urge all Congolese people today to read Heart of Darkness .
Heart of Darkness is the tale of Charles Marlow, an English seaman, who went to the Congo . Marlow, the fictional character and the narrator, told his adventure to his friends on board a cruising yawl called the Nellie on the river Thames overlooking Gravesend while it was immobile.
Are those problems, expressed by Joseph Conrad in Heart of Darkness, still alive today? That is the question.
According to my dear friend Professor Yuko Kurahashi, those problems still exist.
Although some of us are now aware of the link between the extraction of coltan and the misery of the Congolese in the East of their country, we are allowing ourselves to be �blinded' by the comfort that brings the gadgets such mobile phones and laptops. Are we not???
Can these last phrases sum up the new attitudes of the Congolese long-time allies, I hope not. Or it is because the Congolese themselves are not using the right format in propagating their problems.
That is an open question�.
To conclude, I would like to say that we are living in period of greater opportunities. Anything is possible. We should be ready to open our hearts and minds to greater and greater possibilities and also to be prepared to any eventuality. We are living in the information age. Information is becoming available at the click of a mouse. I believe the conscientiousness that led to the formation of The Congo Reform Association in Britain, is still alive.
This speech have been made during the Conference held by Wake Up Congo in London .


In August, ParentsCanada staff headed to SickKids Hospital in Toronto with a truckload of toys to be tested. With smiles on their faces, every kid who attended (and a few who couldn't make it) took home their favourites.
Check out the stellar collection of toys for toddlers in the thumbnails below.


text:
Pathargama is a community development block that forms an administrative division in the Godda subdivision of the Godda district, Jharkhand state, India.

Geography
Pathargama, the eponymous CD block headquarters, is located at .

It is located 19 km from Godda, the district headquarters.

Godda district is a plateau region with undulating uplands, long ridges and depressions. The western portion of the Rajmahal hills passes through the district. The plain areas have lost its once rich forests but the hills still retain some. Kajhia, Sunder and Sakri rivers flow through the district.

Pathargama CD block is bounded by Basantrai and Mahagama CD blocks on the north, Boarijore and Sunderpahari CD blocks on the east,
Godda CD block on the south, and Dhuraiya CD block in Banka district of Bihar on the west.

Pathargama CD block has an area of 155.91 km2.Pathargama police station serves this block. Headquarters of this CD block is at Pathargama village.

Demographics

Population
According to the 2011 Census of India, Pathargama CD block had a total population of 115,662, all of which were rural. There were 59,780 (52%) males and 55,882 (48%) females. Population in the age range 0–6 years was 20,491. Scheduled Castes numbered 13,537 (11.70%) and Scheduled Tribes numbered 18,646 (16.12%).

In 2011 census, Pathargama (village) had a population of 3,490.

Literacy
 census, the total number of literate persons in Pathargama CD block was 58,352 (61.31% of the population over 6 years) out of which 36,571 (63%) were males and 21,781 (37%) were females. The gender disparity (the difference between female and male literacy rates) was 26%.

See also – List of Jharkhand districts ranked by literacy rate

Language and religion
According to the District Census Handbook, Godda, 2011 census, as of 2001, Hindi was the mother-tongue of 603,295 persons forming 57.57% of the population of Godda district, followed by Santali 203,186 persons (19.39%), Urdu 152,275 persons (14.53%) and other languages (with no details)  89,183 perons (8.51%). (In the Census Handbook of Godda district, the mother-tongue information is mentioned as that of Giridih district – it is hoped that it is a printing mistake).

Hindi is the official language in Jharkhand and Urdu has been declared as an additional official language.

According to the District Census Handbook, Godda, 2011 census, Hindus numbered 937,126 and formed 71.34% of the population of Godda district, followed by Muslims 289.182 (22.02%), Christians 37,795 (3.88%), other religions 47,407 (3.61%), religion not stated 2,041 (0.16%).

Rural poverty
40-50% of the population of Godda district were in the BPL category in 2004–2005, being in the same category as Giridih, Koderma and Hazaribagh districts. Rural poverty in Jharkhand declined from 66% in 1993–94 to 46% in 2004–05. In 2011, it has come down to 39.1%.

Economy

Livelihood

In Pathargama CD block in 2011, amongst the class of total workers, cultivators numbered 16,965 and formed 33.33%, agricultural labourers numbered 26,866 and formed 52.79%, household industry workers numbered 1,060 and formed 1.96% and other workers numbered 6,065 and formed 11.92%.  Total workers numbered 50,896 and formed 44.00% of the total population. Non-workers numbered 64,766 and formed  56.00% of total population.

Note: In the census records a person is considered a cultivator, if the person is engaged in cultivation/ supervision of land owned. When a person who works on another person's land for wages in cash or kind or share, is regarded as an agricultural labourer. Household industry is defined as an industry conducted by one or more members of the family within the household or village, and one that does not qualify for registration as a factory under the Factories Act. Other workers are persons engaged in some economic activity other than cultivators, agricultural labourers and household workers.  It includes factory, mining, plantation, transport and office workers, those engaged in business and commerce, teachers and entertainment artistes.

Infrastructure
There are 146 inhabited villages in Pathargama CD block. In 2011, 65 villages had power supply. 14 villages had tap water (treated/ untreated), 95 villages had well water (covered/ uncovered), 116 villages had hand pumps, and 27 villages did not have drinking water facility. 19 villages had post offices, 5 villages had sub post offices, 14 villages had telephones (land lines), 28 villages had public call offices and 60 villages had mobile phone coverage. 111 villages had pucca (paved) village roads, 18 villages had bus service (public/ private), 10 villages had autos/ modified autos, 15 villages had taxis/ vans, 23 villages had tractors, 5 villages had navigable waterways. 6 villages had bank branches, 1 village had ATMs, 6 villages had agricultural credit societies, 30 villages had cinema/ video halls, 31 villages had public libraries, public reading room. 58 villages had public distribution system, 42 villages had weekly haat (market) and 52 villages had assembly polling stations.

Agriculture
Around 80% of the population depends on agriculture, the main economic activity of the district but lack of irrigation facilities is a major constraint in raising the existing low levels of productivity. A sizable population is also engaged in animal husbandry and cottage industries.
The livelihood scenario presented above indicates that a large population depends on agriculture. In Pathargama CD block 74.70% of the total area is cultivable area and 11.52% of the cultivable area is irrigated area.

Backward Regions Grant Fund
Godda district is listed as a backward region and receives financial support from the Backward Regions Grant Fund.  The fund created by the Government of India is designed to redress regional imbalances in development. As of 2012, 272 districts across the country were listed under this scheme. The list includes 21 districts of Jharkhand.

Education
Pathargama CD block had 17 villages with pre-primary schools, 97 villages with primary schools, 61 villages with middle schools, 13 villages with secondary schools, 5 villages with senior secondary schools, 5 vocational training schools/ ITI, 8 villages with non-formal training centres, 47 villages with no educational facility.
.*Senior secondary schools are also known as Inter colleges in Jharkhand

SBSSPSJ College was established at Pathargama in 1980. It is affiliated with Sido Kanhu Murmu University. It offers both honours and general courses in arts, science and commerce.

Healthcare
Pathargama CD block had 4 villages with primary health centres, 15 villages with primary health subcentres, 3 village with maternity and child welfare centre, 1 village with TB clinic, 2 villages with allopathic hospitals, 1 village with dispensary, 1 village with veterinary hospital, 1 village with family welfare centre, 3 villages with medicine shops.
.*Private medical practitioners, alternative medicine etc. not included

References

Community development blocks in Godda district

redpajama_set_name: RedPajamaWikipedia


their sound is a heavy lullaby we wade knee deep in.
collecting in my ears is sea flooding in, determined.
a comfort we think we've had before but cannot place.
light, grows vast as thought itself and we remain consumed.
waits pocketed, yearning to feel the ground.
Birds are made of light.
crystallises on solid objects: twigs, rooftops.
or the whole iridescence of a magpie's wing.
Their bodies are different from ours.
fly more slowly, perch for longer, grey at the wings, get fat.
are disappointed with their trophy: just claws and guts.
although you can't hum the tune.
new ones will condense again at first light.
and falling, or rising. It's hard to tell.
at last the beauty of the kill.
a single white flash on his wing tips.
a harmonic of a third.
This hare has ears bigger than her head.
This hare creeps close to the ground.
a zigzag back over her tracks.
This hare will not burrow deep.
she holes up until night.
This hare will box her mate flat.
until she is ready to take him.
with a promise of love and a sack of fertility.
and lunch on her young.
an hour after sunrise, or perhaps before sunset.
it seems our home is – ordinary.
the froth of waves or penguins' bibs, a marbled bust.
with a carefully chosen satin emulsion of average starlight.
before sunset, is the spectrum of light from the Milky Way.
from a child's god-like hand.
At night, I see them through the window.
White-faced beggars. Or wimpled messengers.
the way they lean towards me, nodding.
where everything is made of hurting light.
backdrop of my garden, so they can rest.
in a white language I'm trying to translate.
What happened to Karen McCarthy Woolf?


> But it can't go because there's no working alternative.
Well... attached is a prototype of a yum plugin to do this sort of stuff.
# Copyright © 2009 Red Hat, Inc.
# This needs to be in the metadata somewhere. For a POC, this works.
#print "YOU GET TO DRINK FROM THE FIRE HOSE!"


text:
Q: How to get content of tags in array? I'm using woocommerce and a function returns item data in the below format

options:

redwood-120mm-x-28mm

length:

3.6

linear metres:

500

I want to input this data into an array, like the following;
array("options:" => "redwood-120mm-x-28mm", "length:"=> "3.6", "linear metres:" => "500");

How do  i do this?
This is the function:
global $woocommerce;
     foreach ( $woocommerce->cart->get_cart() as $cart_item_key => $cart_item ) {
        echo $woocommerce->cart->get_item_data( $cart_item );

     }
}

A: You can do it by regular expression, maybe you want to give a shot for DOM in PHP.
My explanation is in the code in comments.
//String to parse
$string = '

options:

redwood-120mm-x-28mm

length:

3.6

linear metres:

500

';

//Keys, you want to find
$keys = array('options', 'length', 'linear metres');

//The result array
$result = array();

//Loop through the keys
foreach ($keys as $key) {
    //Insert the result into the result array
    $result[$key] = getValueByKey($key, $string);
}

//Show results
var_dump($result);

function getValueByKey($key, $string) {
    //The pattern by key
    $pattern = '/
' . $key . ':<\/dt>
(.*?)<\/dd>/i';

    //Initialize a match array
    $matches = array();

    //Do the regular expression
    preg_match($pattern, $string, $matches);
    if (!empty($matches[1])) {
        //If there are match, then return with it
        return $matches[1];
    }
    //Otherwise return with false
    return false;
}

Output is:
array (size=3)
  'options' => string 'redwood-120mm-x-28mm' (length=20)
  'length' => string '3.6' (length=3)
  'linear metres' => string '500' (length=3)

redpajama_set_name: RedPajamaStackExchange


We are cultural workers and healers committed to helping each member of our community live fully, holistically, and in alignment/accordance with his or her divine purpose.
Our processes are directed towards healing ancestral and historical wounds by engaging with our pasts and histories (the "orthodox", unwritten, oral, silenced, or disappeared) with compassion, love, forgiveness, and gratitude.
Throughout the year we come together to meditate and do healing work for ourselves, each other, and our various communities.
We utilize research and scholarship, the arts, good old common sense, childlike laughter, and the wisdom of our elders and ancestors as we journey on our paths.


According to a new Huffington Post Poll, only 25% of women believe the accusations against Brett Kavanaugh.
This poll shows that the accusations by Christine Ford don't provide enough proof for people to believe them. This also explains why the Democrats are trying their best to search for another accuser to 'finish the job' on stopping Brett Kavanaugh from being confirmed.