there are alternative algorithms for segment intersection, e.g., Mulmuley's method. Do they generalize more easily to curved segments
more general arcs, e.g., general conic sections or Bezier curves.
diamond operator and zeros of arbitrary polynomials.
closed formulae for degree three and four polynomials
Voronoi diagrams of line segments, Voronoi diagrams of circles, Voronoi diagram of line segments and circles. Primitives. Can these problems be solved by sampling? Assume you have solution of a point sample. Can one derive the true solution from it. Can one recognize that sample is not dense enough?