PROCEDURE PickRandomVertexPair(
        els: EdgeList; 
        trial: CARDINAL;
      ): TrArScene.VertexPair =
      (*
        Picks a random pair of vertices among the endpoints of the 
        edges in "els".
      *)
      VAR n: CARDINAL := 0;
          t: EdgeList := els;
          vp: TrArScene.VertexPair;
      BEGIN
        (* Count edges: *)
        WHILE t # NIL DO INC(n); t := t.rest END;
        <* ASSERT n > 0 *>
        
        (* Pick picking strategy: *)
        IF n <= MaxTrials THEN
          (* Too few edges, just try them out one by one: *)
          t := els;
          FOR k := 1 TO (trial-1) MOD n DO t := t.rest END;
          FOR i := 0 TO 1 DO vp[i] := t.e.vert[i] END
        ELSIF trial = 1 THEN
          (* Pick the longest edge the in direction "dir": *)
          VAR emax: REF TrArScene.Edge := NIL; dmax: REAL := -1.0; 
          BEGIN
            t := els;
            WHILE t # NIL DO
              WITH
                e = t.e,
                u = e.vert[0],
                v = e.vert[1],
                uc = HLR3.ToCartesian(u.wcs),
                vc = HLR3.ToCartesian(v.wcs),
                d = ABS(uc[dir] - vc[dir])
              DO
                IF d > dmax THEN emax := e; dmax := d END;
              END;
              t := t.rest
            END;
            <* ASSERT emax # NIL *>
            FOR i := 0 TO 1 DO vp[i] := emax.vert[i] END
          END;
        ELSIF Random.Subrange(coins, 1, n - 1) <= MaxTrials THEN
          (* Relatively few edges: tend to pick a random edge: *)
          WITH eskip = Random.Subrange(coins, 0, n-1) DO
            t := els;
            FOR k := 1 TO eskip DO t := t.rest END;
            FOR i := 0 TO 1 DO vp[i] := t.e.vert[i] END
          END
        ELSE
          (* Relatively many edges: tend to pick two distinct endpoints at random *)
          REPEAT
            FOR i := 0 TO 1 DO
              WITH
                r = Random.Subrange(coins, 0, 2*n-1),
                eskip = r DIV 2,
                iv = r MOD 2
              DO
                t := els;
                FOR k := 1 TO eskip DO t := t.rest END;
                vp[i] := t.e.vert[iv]
              END
            END
          UNTIL vp[0] # vp[1]
        END;
        RETURN vp
      END PickRandomVertexPair;
      
    PROCEDURE NiceCut(els: EdgeList; trial: CARDINAL): BOOLEAN =
      (*
        TRUE if the current "val" fields define a reasonably
        balanced cut of the edges in "els".
      *)
      VAR ne, nn, np: CARDINAL := 0;
          t: EdgeList := els;
      <* FATAL Wr.Failure, Thread.Alerted *>
      BEGIN
        (* If there are at most two edges, the cut is balanced: *)
        IF t = NIL
        OR t.rest = NIL
        OR t.rest.rest = NIL
        THEN 
          RETURN TRUE
        END;
        (* Count edges on each side of cut: *)
        WHILE t # NIL DO 
          WITH
            e = t.e,
            s0 = e.vert[0].val,
            s1 = e.vert[1].val
          DO
            INC(ne);
            IF s0*s1 < 0.0d0 THEN
              (* Edge will be split: *)
              INC(nn); INC(np)
            ELSE
              (* Edge will not be split: *)
              IF s0 < 0.0d0 OR s1 < 0.0d0 THEN
                INC(nn)
              ELSIF s0 > 0.0d0 OR s1 > 0.0d0 THEN
                INC(np)
              ELSE
                (* Edge lies on cutting plane *)
              END
            END
          END;
          t := t.rest
        END;
        IF Debug THEN
          Wr.PutChar(stderr, '[');
          Wr.PutText(stderr, Fmt.Int(ne)); 
          Wr.PutChar(stderr, '>');
          Wr.PutText(stderr, Fmt.Int(nn)); 
          Wr.PutChar(stderr, ':');
          Wr.PutText(stderr, Fmt.Int(np));
          Wr.PutChar(stderr, ']');
        END;
        
        (* If we have tried all edges, the cut is balanced: *)
        IF ne <= MaxTrials AND trial >= MaxTrials THEN
          RETURN TRUE
        END;
        
        (* Decide whether cut is balanced: *)
        WITH 
          sne = CEILING(Math.sqrt(FLOAT(ne, LONGREAL)))
        DO
          RETURN
            (nn + np <= ne + sne) AND
            (4 * ABS(nn - np) <= nn + np)
        END
      END NiceCut;
      
    UNTIL valid AND (trial >= MaxTrials OR NiceCut(inx.e, trial));
    
    CONST
      MaxTrials = 5;