Applications of random sampling in computational geometry, II

No abstract is available for this paper.

• Publication year

  1988

• Venue

  SCG '88

• Publication date

  1988-01-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/73393.73394
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Combinatorial complexity bounds for arrangements of curves and surfaces

  2015cited by this paper
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms

  1990cited by this paper
• Building Voronoi Diagrams for Convex Polygons in Linear Expected Time

  1990cited by this paper
• Construction of ɛ-nets

  1990cited by this paper
• Polling: a new randomized sampling technique for computational geometry

  1989cited by this paper
• Construction of epsilon nets

  1989cited by this paper
• A deterministic algorithm for partitioning arrangements of lines and its application

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

  1988cited by this paper
• A fast planar partition algorithm: Part I

  1988cited by this paper
• Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incremental

  1988cited by this paper
• A fast las vegas algorithm for triangulating a simple polygon

  1988cited by this paper
• A fast planar partition algorithm. I

  1988cited by this paper
• Partition trees for triangle counting and other range searching problems

  1988cited by this paper
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms

  1988cited by this paper
• An O(n log log n)-Time Algorithm for Triangulating a Simple Polygon

  1988cited by this paper
• A Las Vegas algorithm for linear programming when the dimension is small

  1988cited by this paper
• A geometric consistency theorem for a symbolic perturbation scheme

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

  1988cited by this paper
• Algorithms in Combinatorial Geometry

  1987influential reference
• Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension

  1987cited by this paper
• New applications of random sampling in computational geometry

  1987cited by this paper
• ɛ-nets and simplex range queries

  1987cited by this paper
• Constructing higher-dimensional convex hulls at logarithmic cost per face

  1986cited by this paper
• Epsilon-nets and simplex range queries

  1986influential reference
• The Ultimate Planar Convex Hull Algorithm?

  1986influential reference
• The number of small semispaces of a finite set of points in the plane

  1986cited by this paper
• More onk-sets of finite sets in the plane

  1986cited by this paper
• A probabilistic algorithm for the post office problem

  1985cited by this paper
• Halfspace range search: an algorithmic application of K-sets

  1985cited by this paper
• Computational Geometry

  1985influential reference
• On the Number of k-Subsets of a Set of n Points in the Plane

  1984cited by this paper
• On k-hulls and related problems

  1984cited by this paper
• Linear Programming in Linear Time When the Dimension Is Fixed

  1984cited by this paper
• The Number of Small Semispaces of a Finite Set of Points in the Plane

  1984cited by this paper
• The power of geometric duality

  1983cited by this paper
• Primitives for the manipulation of general subdivisions and the computation of Voronoi

  1983cited by this paper
• On the shape of a set of points in the plane

  1983cited by this paper
• Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams

  1983cited by this paper
• Constructing arrangements of lines and hyperplanes with applications

  1983cited by this paper
• A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions

  1981cited by this paper
• Finding the Intersection of two Convex Polyhedra

  1978cited by this paper
• Convex hulls of finite sets of points in two and three dimensions

  1977cited by this paper
• Probabilistic Methods in Combinatorics

  1974cited by this paper
• Quicksort

  1962cited by this paper
• Beweis einer Vermutung von A. Vázsonyi

  1956cited by this paper

• Multi-objective reinforcement learning for provably incentivising alignment with value systems

  2026cites this paper
• Delaunay Triangulations with Predictions

  2026influential citation
• UF-CDDFM: A unified framework for code defect detection using multi-modal inputs and few-shot learning

  2026cites this paper
• Sublevels in arrangements and the spherical arc crossing number of complete graphs

  2025cites this paper
• On the Theoretical Limitations of Embedding-Based Retrieval

  2025cites this paper
• Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework

  2025influential citation
• Stabbing non-piercing sets and face lengths in large girth plane graphs

  2025cites this paper
• Largest dyadic dual VC-dimension of non-piercing families

  2025cites this paper
• Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers

  2025cites this paper
• Optimal Parallel Algorithms for Convex Hulls in 2D and 3D under Noisy Primitive Operations

  2025cites this paper
• Efficiently approximating the minimum-volume bounding box of a point set in three dimensions

  2025cites this paper
• Shelling and Sinking Graphs on the Sphere

  2025influential citation
• A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation

  2025cites this paper
• Probabilistic Robustness Analysis in High Dimensional Space: Application to Semantic Segmentation Network

  2025cites this paper
• Polychromatic Coloring of Tuples in Hypergraphs

  2025cites this paper
• A Polynomial-Time Algorithm for Computing the Exact Convex Hull in High-Dimensional Spaces

  2025cites this paper
• On the B-differential of the componentwise minimum of two affine vector functions

  2025cites this paper
• Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane

  2024cites this paper
• Semi-Algebraic Off-line Range Searching and Biclique Partitions in the Plane

  2024influential citation
• Statistical sampling method to verify the homogeneity of full-scale cement-solidified radioactive waste

  2024cites this paper
• Deephullnet: a deep learning approach for solving the convex hull and concave hull problems with transformer

  2024cites this paper
• A novel algorithm for finding convex hull of a generic polygon with simulation of progressively supporting elastic lines

  2024cites this paper
• Classification of Environmental Strategies by Corporations

  2024cites this paper
• PEMETAAN GAME EDUKASI TERHADAP PEMIKIRAN INVENTIF SISWA

  2024cites this paper
• Combinatorial optimization of the coefficient of determination

  2024influential citation
• Enumeration of Intersection Graphs of x-Monotone Curves

  2024influential citation
• Lower Envelopes of Surface Patches in 3-Space

  2024cites this paper
• Improved Bounds for Point Selections and Halving Hyperplanes in Higher Dimensions

  2024cites this paper
• Deciphering refactoring branch dynamics in modern code review: An empirical study on Qt

  2024cites this paper
• Carving Polytopes with Saws in 3D

  2024cites this paper
• What Else Can Voronoi Diagrams Do For Diameter In Planar Graphs?

  2023cites this paper
• Parameter Identification of Bivariate Fractal Interpolation Surfaces by Using Convex Hulls

  2023cites this paper
• Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs

  2023cites this paper
• A comparison of sequential Delaunay triangulation algorithms. (English)

  2023cites this paper
• Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain

  2023cites this paper
• Distributed data filtering and modeling for fog and networked manufacturing

  2023cites this paper
• Polygon Detection from a Set of Lines

  2023cites this paper
• Hopcroft’s Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision Trees

  2023influential citation
• Unbounded Regions of High-Order Voronoi Diagrams of Lines and Line Segments in Higher Dimensions

  2023cites this paper
• Particle morphology characterization of waste-tyre-stabilized rock aggregates via computational geometric modellings

  2023cites this paper
• Computing k-Crossing Visibility through k-levels

  2023influential citation
• Fast Approximation Algorithms for Piercing Boxes by Points

  2023cites this paper
• An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism

  2023cites this paper
• An Algorithm for Random Tessellation Using a Steppe Fire Model

  2023cites this paper
• Online multivariate changepoint detection: leveraging links with computational geometry

  2023cites this paper
• On polynomials associated to Voronoi diagrams of point sets and crossing numbers

  2023cites this paper
• Polytope shaping while preserving invariance

  2022cites this paper
• Sampling and the Moments Technique

  2022cites this paper
• Massively Parallel Computation on Embedded Planar Graphs

  2022influential citation
• A Finite Algorithm for the Realizabilty of a Delaunay Triangulation

  2022cites this paper
• Code Review Practices for Refactoring Changes: An Empirical Study on OpenStack

  2022cites this paper
• Fast computation of critical planes for fatigue life analysis of metals

  2022cites this paper
• Voronoi Diagrams of Arbitrary Order on the Sphere

  2022cites this paper
• Constrained random matching

  2022cites this paper
• On Exact Computation of Tukey Depth Central Regions

  2022cites this paper
• Voronoi diagrams from closed bisecting curves. (

  2022cites this paper
• ParGeo: A Library for Parallel Computational Geometry

  2022cites this paper
• Massively Parallel Computation and Sublinear-Time Algorithms for Embedded Planar Graphs

  2022influential citation
• Sparsifying Disk Intersection Graphs for Reliable Connectivity

  2022influential citation
• On Finding Rank Regret Representatives

  2022cites this paper
• Generic Techniques for Building Top-k Structures

  2022cites this paper
• Conflict-Free Colouring of Subsets

  2022influential citation
• An efficient planar incremental convex hull algorithm to find the edges of the boundary polygon of the convex hull of a set of points

  2021cites this paper
• Dynamic Geometric Set Cover, Revisited

  2021cites this paper
• Active Learning for Massively Parallel Translation of Constrained Text into Low Resource Languages

  2021cites this paper
• An Empirical Study towards dealing with Noise and Class Imbalance issues in Software Defect Prediction

  2021cites this paper
• Constructing Many Faces in Arrangements of Lines and Segments

  2021cites this paper
• An empirical study toward dealing with noise and class imbalance issues in software defect prediction

  2021cites this paper
• Railway vehicle bearings risk monitoring based on normal region estimation for no-fault data situations

  2021cites this paper
• Finding Relevant Points for Nearest-Neighbor Classification

  2021cites this paper
• Clique-Based Separators for Geometric Intersection Graphs

  2021cites this paper
• The edge labeling of higher order Voronoi diagrams

  2021cites this paper
• (Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems

  2021influential citation
• Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions

  2021cites this paper
• Guaranteeing the Learning of Ethical Behaviour through Multi-Objective Reinforcement Learning

  2021cites this paper
• Multi-Objective Reinforcement Learning for Designing Ethical Environments

  2021cites this paper
• Window queries for intersecting objects, maximal points and approximations using coresets

  2021cites this paper
• Union of Hypercubes and 3D Minkowski Sums with Random Sizes

  2021cites this paper
• Computational Geometry-Based Surface Reconstruction for Volume Estimation: A Case Study on Magnitude-Frequency Relations for a LiDAR-Derived Rockfall Inventory

  2021cites this paper
• Voronoi Diagrams

  2021cites this paper
• Sunflowers in Set Systems of Bounded Dimension

  2021cites this paper
• The Maximum Exposure Problem

  2021cites this paper
• On Geometric Priority Set Cover Problems

  2021cites this paper
• Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points

  2021cites this paper
• A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures

  2021cites this paper
• Voronoi Diagrams in the Hilbert Metric

  2021cites this paper
• More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time

  2021cites this paper
• Algorithmic Bayesian persuasion with combinatorial actions

  2021cites this paper
• Computing the Multicover Bifiltration

  2021cites this paper
• Counting Cells of Order-k Voronoi Tessellations in ℝ³ with Morse Theory

  2021cites this paper
• Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees

  2021influential citation
• Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices

  2021cites this paper
• Cluster-based data filtering for manufacturing big data systems

  2021cites this paper
• COMBINATORIAL BOUNDS IN DISTAL STRUCTURES

  2021cites this paper
• Optimal Window Queries on Line Segments using the Trapezoidal Search DAG

  2021cites this paper
• Convex Decreasing Algorithms: Distributed Synthesis and Finite-Time Termination in Higher Dimension

  2020cites this paper
• Polyhedral Circuits and Their Applications

  2020cites this paper
• Constructing Planar Support for Non-Piercing Regions

  2020cites this paper
• A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes

  2020cites this paper
• Dimensionality reduction for k-distance applied to persistent homology

  2020cites this paper