Randomized external-memory algorithms for some geometric problems

No abstract is available for this paper.

• Publication year

  1998

• Venue

  SCG '98

• Publication date

  1998-06-07

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/276884.276914
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• LEDA-SM a platform for secondary memory computations

  1999cited by this paper
• On sorting strings in external memory (extended abstract)

  1997cited by this paper
• LEDA: a platform for combinatorial and geometric computing

  1997influential reference
• Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms

  1997cited by this paper
• BSP-Like External-Memory Computation

  1997cited by this paper
• Simple randomized mergesort on parallel disks

  1996cited by this paper
• On computing Voronoi diagrams by divide-prune-and-conquer

  1996cited by this paper
• Report of the Working Group on Storage I/O Issues in Large-Scale Computing

  1996cited by this paper
• Strategic directions in storage I/O issues in large-scale computing

  1996cited by this paper
• I/O Efficient Scientific Computation Using TPIE

  1995cited by this paper
• A platform for combinatorial and geometric computing

  1995cited by this paper
• Greed sort: optimal deterministic sorting on parallel disks

  1995cited by this paper
• External-memory graph algorithms

  1995cited by this paper
• Computing faces in segment and simplex arrangements

  1995cited by this paper
• Supporting I/O-efficient scientific computation in TPIE

  1995cited by this paper
• A fully-dynamic data structure for external substring search

  1995cited by this paper
• Erratum: Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems

  1994cited by this paper
• The I/O subsystem/spl minus/a candidate for improvement

  1994cited by this paper
• The I/O Subsystem - A Candidate for Improvement: Guest Editor's Introduction

  1994cited by this paper
• External-memory computational geometry

  1993influential reference
• An optimal convex hull algorithm in any fixed dimension

  1993cited by this paper
• Computational geometry - an introduction through randomized algorithms

  1993influential reference
• Backwards Analysis of Randomized Geometric Algorithms

  1993cited by this paper
• Product range spaces, sensitive sampling, and derandomization

  1993cited by this paper
• Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems

  1992cited by this paper
• Fundamentals of spatial information systems

  1992cited by this paper
• Randomized parallel algorithms for trapezoidal diagrams

  1992cited by this paper
• RANDOMIZED GEOMETRIC ALGORITHMS

  1992cited by this paper
• Dynamic point location in arrangements of hyperplanes

  1991cited by this paper
• Applications of spatial data structures - computer graphics, image processing, and GIS

  1990cited by this paper
• Concrete and Abstract Voronoi Diagrams

  1990cited by this paper
• Cutting hyperplane arrangements

  1990cited by this paper
• Applications of random sampling in computational geometry, II

  1988cited by this paper
• An optimal algorithm for intersecting line segments in the plane

  1988cited by this paper
• The input/output complexity of sorting and related problems

  1988cited by this paper
• A deterministic view of random sampling and its use in geometry

  1988influential reference
• A fast planar partition algorithm. I

  1988cited by this paper
• Algorithms in Combinatorial Geometry

  1987cited by this paper
• Computational Geometry

  1985cited by this paper
• WHO Technical Report

  1954cited by this paper

• I/O-efficient map overlay and point location in low-density

  2016cites this paper
• The Parallel Disk Model of Aggarwal / Vitter

  2011cites this paper
• Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions

  2010cites this paper
• Scalable algorithms for large high-resolution terrain data

  2010cites this paper
• Guarding Rectangular Partitions

  2009cites this paper
• I/O-efficient algorithms for computing planar geometric spanners

  2008cites this paper
• Optimizing locality and parallelism through program reorganization

  2008cites this paper
• External Memory Planar Point Location with Logarithmic Updates

  2008cites this paper
• I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions

  2007cites this paper
• TerraStream: from elevation data to watershed hierarchies

  2007cites this paper
• Engineering a compact parallel delaunay algorithm in 3D

  2006cites this paper
• I/o efficient algorithms and applications in geographic information systems

  2006cites this paper
• Compact data structures with fast queries

  2006cites this paper
• Approches fonctionnelles de la programmation parallèle et des méta-ordinateurs. Sémantiques, implantations et certification. (Functional approaches of parallel programming and méta-computers. Semantics, implementations and certification)

  2005cites this paper
• Compact representations of simplicial meshes in two and three dimensions

  2005cites this paper
• I/O-Efficient Construction of Constrained Delaunay Triangulations

  2005influential citation
• Approximate range searching using binary space partitions

  2004cites this paper
• Parallel Out-of-Core Sorting: The Third Way

  2004cites this paper
• Parallel I/O in Bulk-Synchronous Parallel ML

  2004cites this paper
• TR A 1 / 0 6 Efficient Constrained Delaunay Triangulation for Large Spatial Databases

  2004cites this paper
• Algorithms for Memory Hierarchies

  2003cites this paper
• I/O-efficient point location using persistent B-trees

  2003cites this paper
• External Memory Geometric Data Structures

  2002cites this paper
• Bulk Synchronous Parallel Algorithms for the External Memory Model

  2002cites this paper
• Design and analysis of sequential and parallel single-source shortest-paths algorithms

  2002cites this paper
• Static optimality theorem for external memory string access

  2002cites this paper
• External memory algorithms and data structures: dealing with massive data

  2001cites this paper
• External Memory Data Structures (invited Paper)

  2001cites this paper
• External Memory Data Structures

  2001influential citation
• I/O-efficient dynamic planar point location (extended abstract)

  2000influential citation
• Planar point location for large data sets: to seek or not to seek

  2000cites this paper
• The Input, Preparation, and Distribution of Data for Parallel GIS Operations (Research Note)

  2000cites this paper
• I/o-eecient Dynamic Planar Point Location

  1999cites this paper
• On range reporting, ray shooting and k-level construction

  1999cites this paper
• I/O-optimal computation of segment intersections

  1999cites this paper
• Reducing I/O complexity by simulating coarse grained parallel algorithms

  1999cites this paper
• Efficient Searching with Linear Constraints 1

  1999cites this paper
• Efficient searching with linear constraints

  1998cites this paper
• External memory algorithms

  1998cites this paper
• Eecient Searching with Linear Constraints

  1997cites this paper
• Eecient Searching with Linear Constraints

  1997cites this paper
• cient Searching with Linear Constraints

  year unknowncites this paper
• Journal of Graph Algorithms and Applications I/o-efficient Algorithms on Near-planar Graphs 504 Haverkort & Toma I/o-efficient Algorithms on Near-planar Graphs

  year unknowncites this paper
• Paradigms for EÆcient Design of External Memory Algorithms

  year unknowncites this paper