Now showing items 1-4 of 4

    • A Method for Proving Lower Bounds for Certain Geometric Problems 

      Seidel, Raimund (Cornell University, 1984-02)
      We prove lower bounds for a number of geometric problems. Our results show that certain types of additional input information cannot possibly permit faster solutions for these problems. The main idea in all our lower ...
    • Output-Size Sensitive Algorithms for Constructive Problems in Computational Geometry 

      Seidel, Raimund (Cornell University, 1986-09)
      In computer science the efficiency of algorithms is usually measured in terms of the size of the input. The output size, on the other hand, has been used for this purpose rather infrequently, except in certain enumerative ...
    • The Ultimate Planar Convex Hull Algorithm ? 

      Kirkpatrick, David G.; Seidel, Raimund (Cornell University, 1983-10)
      We present a new planar convex hull algorithm with worst case time complexity $O(n \log H)$ where $n$ is the size of the input set and $H$ is the size of the output set, i.e. the number of vertices found to be on the ...
    • Voronoi Diagrams and Arrangements 

      Edelsbrunner, Herbert; Seidel, Raimund (Cornell University, 1985-03)
      We propose a uniform and general framework for defining and dealing with Voronoi Diagrams. In this framework a Voronoi Diagram is a partition of a domain $D$ induced by a finite number of real valued functions on $D$. ...