title: Simple algorithm to compute vertical map of set of segments?
body: <p>The paper <a href="http://www.cs.princeton.edu/~chazelle/pubs/IntersectLineSegments.pdf" rel="nofollow">An optimal algorithm for intersecting line segments in the plane</a> by Chazelle and Edelsbrunner defines the "vertical map" of a set of segments as</p>
  
  <blockquote>
    <p>the planar subdivision obtained by drawing a rectangular frame around the
    segments and connecting by a vertical line segment every endpoint to
    the edges immediately above and below</p>
  </blockquote>
  
  <p>(It really is easier to understand looking at the diagram on the top of page 3).</p>
  
  <p>They make the comment</p>
  
  <blockquote>
    <p>we do not know of any <em>simple</em> algorithm, no matter how slow, for
    computing the vertical map of a set of segments</p>
  </blockquote>
  
  <p>To me this seems confusing, because I immediately thought of a simple algorithm to do so:</p>
  
  <pre><code>Iterate through every endpoint p
    Iterate through every other segment s
      t=intersection(s, vertical line through p)
      keep track of the closest t above and below p
  
    add the closest point above and the closest point below and connect them with a segment
  </code></pre>
  
  <p>And then we're done?  I mean, this would only be O(N^2) running time, not even that bad.</p>
  
  <p>What more could they mean that this algorithm doesn't satisfy?  Do they expect to find the intersection points as well?  Wouldn't an O(N^2) pairwise intersection check do that?  Do they want to enumerate the subdivisions of the plane?  Couldn't that just be done very simply using standard algorithms to go from points+edges to faces? e.g. by walking around the border of the face?</p>
  
  <p>Is there something I'm missing?</p>