Constructing higher-dimensional convex hulls at logarithmic cost per face

No abstract is available for this paper.

• Publication year

  1986

• Venue

  Symposium on the Theory of Computing

• Publication date

  1986-11-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/12130.12172
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Ultimate Planar Convex Hull Algorithm?

  1986cited by this paper
• Finding the Convex Hull Facet by Facet

  1985cited by this paper
• Computational Geometry

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

  1984influential reference
• Lower bounds for algebraic computation trees

  1983cited by this paper
• The Complexity of Vertex Enumeration Methods

  1983cited by this paper
• Application of computational geometry to pattern recognition problems

  1982cited by this paper
• A Lower Bound to Finding Convex Hulls

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

  1981cited by this paper
• A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets

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

  1977cited by this paper
• An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set

  1972cited by this paper
• Shellable Decompositions of Cells and Spheres.

  1971cited by this paper
• Convex Polytopes and the Upper Bound Conjecture

  1971cited by this paper

• Maximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear Programs with Convex Hull as the Intermediate Representation

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

  2023cites this paper
• Voronoi Diagrams

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

  2021cites this paper
• Fence GAN: Towards Better Anomaly Detection

  2019cites this paper
• A polytree based coupling method for non-matching meshes in 3D

  2019cites this paper
• Rotating Supporting Hyperplanes and Snug Circumscribing Simplexes

  2018cites this paper
• Location Problems with k-max Functions - Modelling and Analysing Outliers in Center Problems

  2018cites this paper
• On the expected complexity of the 3-dimensional Voronoi diagram

  2017cites this paper
• On ill-conceived initialization in archetypal analysis

  2017cites this paper
• An Expected Linear 3-Dimensional Voronoi Diagram Algorithm

  2017cites this paper
• Objektbasierte Segmentierung und Klassifikation von LiDAR-Punktwolken

  2017cites this paper
• 26 CONVEX HULL COMPUTATIONS

  2017cites this paper
• On ill-conceived initialization in archetypal analysis

  2017cites this paper
• Bridging the Gap in Grasp Quality Evaluation and Grasp Planning

  2017cites this paper
• Partial convex hull algorithms for efficient grasp quality evaluation

  2016cites this paper
• Meshing Piecewise Smooth Complexes

  2016cites this paper
• Scalable Algorithms for Data and Network Analysis

  2016cites this paper
• Higher-dimensional modelling of geographic information

  2016cites this paper
• Geometric Computing over Uncertain Data

  2015cites this paper
• Nuevo Algoritmo para la Construcción de la Envolvente Convexa en el Plano

  2015cites this paper
• Optimizations for sampling-based motion planning algorithms

  2014cites this paper
• Convex Hulls Under Uncertainty

  2014cites this paper
• A New Approach to Output-Sensitive Construction of Voronoi Diagrams and Delaunay Triangulations

  2014cites this paper
• A Survey of Computational Geometry

  2014influential citation
• Computing Volumes and Convex Hulls: Variations and Extensions

  2014cites this paper
• Convex hulls of spheres and convex hulls of disjoint convex polytopes

  2013cites this paper
• Monotone Multivariate Interpolation of Scattered Data Using Nested Hypercubes

  2013cites this paper
• Quantifier Elimination for Conjunctions of Linear Constraints via a Convex Hull Algorithm

  2013cites this paper
• On the bit-complexity of sparse polynomial and series multiplication

  2013cites this paper
• Construção e edição de diagramas de Voronoi na esfera

  2013cites this paper
• Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension

  2013cites this paper
• Visibility Problems Concerning One-Sided Segments

  2012cites this paper
• A new approach to output-sensitive voronoi diagrams and delaunay triangulations

  2012cites this paper
• High performance GPGPU based system for matching people in a live video feed

  2012cites this paper
• Delaunay Mesh Generation

  2012cites this paper
• Gcd of multivariate polynomials via Newton polytopes

  2011influential citation
• Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension

  2011cites this paper
• Certifying algorithms

  2011cites this paper
• - 1-APPLICATION OF PROXIMITY GRAPHS TO EDITING NEAREST NEIGHBOR DECISION RULES *

  2010cites this paper
• Optimal Partition Trees

  2010cites this paper
• Practical Ways to Accelerate Delaunay Triangulations

  2010cites this paper
• Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes

  2009cites this paper
• On feasibility boundaries of electrical power grids in steady state

  2009cites this paper
• Identification of piecewise affine systems by means of fuzzy clustering and competitive learning

  2008cites this paper
• Computational Geometry Analysis of Quantum State Space and Its Applications

  2008cites this paper
• On-line stable state determination in decentralized power grid management

  2008cites this paper
• Quantum bounds on Bell inequalities

  2008cites this paper
• Voronoi Diagrams for Quantum States and Its Application to a Numerical Estimation of a Quantum Channel Capacity

  2008cites this paper
• Computing Markov bases, Gröbner bases, and extreme rays

  2007cites this paper
• Mathematisches Forschungsinstitut Oberwolfach Report No . 4 / 2007 Geometric and Topological Combinatorics Organised

  2007cites this paper
• Primal Dividing and Dual Pruning: Output-Sensitive Construction of 4-d Polytopes and 3-d Voronoi Diagrams

  2007cites this paper
• Title: Associate Professor of Information Science

  2007cites this paper
• Complexity of Delaunay triangulation for points on lower-dimensional polyhedra

  2007cites this paper
• INDEPENDENCE POLYNOMIALS OF CIRCULANT GRAPHS

  2007cites this paper
• Greedy Basis Pursuit

  2007cites this paper
• Average-Case Analysis of the Double Description Method and the Beneath-Beyond Algorithm

  2007influential citation
• Higher Dimensional Convex Hull Algorithms

  2006cites this paper
• Combinatorial Geometry with Algorithmic Applications

  2006cites this paper
• Geometric algorithms for delineating geographic regions

  2006cites this paper
• Sparse coding via geometry

  2005cites this paper
• Certifying Algorithms (A Paper under Construction)

  2005cites this paper
• Multi-Dimensional Scattered Ranking Methods for Geographic Information Retrieval*

  2005cites this paper
• Efficient computation of feedback controllers for constrained systems

  2004cites this paper
• Distributed Ranking Methods for Geographic Information Retrieval

  2004cites this paper
• Towards in-place geometric algorithms and data structures

  2004influential citation
• Dual Representations of Non-Parametric Technologies and Measurement of Technical Efficiency

  2003cites this paper
• A Minimalist ’ s Implementation of the 3-d Divide-and-Conquer Convex Hull Algorithm

  2003cites this paper
• Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima

  2003cites this paper
• about the Internet and Networking : 2010 – 2019

  2003cites this paper
• REINFORCEMENT LEARNING IN THE JOINT SPACE: VALUE ITERATION IN WORLDS WITH CONTINUOUS STATES AND ACTIONS

  2003cites this paper
• Incremental construction properties in dimension two--shellability, extendable shellability and vertex decomposability

  2003cites this paper
• REINFORCEMENT LEARNING IN THE JOINT SPACE: VALUE ITERATION IN WORLDS WITH CONTINUOUS STATES AND ACTIONS by

  2003cites this paper
• Enumerating Triangulations in General Dimensions

  2002cites this paper
• Some Algorithmic Problems in Polytope Theory

  2002cites this paper
• Combinatorics of Triangulations Title: Associate Professor of Information Science

  2001cites this paper
• A method of transferring polyhedron between the intersection-form and the sum-form

  2001cites this paper
• Dense Point Sets Have Sparse Delaunay Triangulations or “... But Not Too Nasty”

  2001cites this paper
• Dense point sets have sparse Delaunay triangulations

  2001influential citation
• Extended convex hull

  2001cites this paper
• Automatic Surface Reconstruction from Point Sets in Space

  2000cites this paper
• Chapter 5 – Voronoi Diagrams*

  2000cites this paper
• Frequently Asked Questions in Polyhedral Computation

  2000cites this paper
• Sweep algorithms for constructing higher-dimensional constrained Delaunay triangulations

  2000cites this paper
• Arrangements and Their Applications

  2000cites this paper
• Combinatorics of Constructible Complexes

  2000influential citation
• A method of transferring cones of intersection form to cones of sum form and its applications in data envelopment analysis models

  2000cites this paper
• On deletion in Delaunay triangulations

  1999cites this paper
• Hölder Distance Function and Measurement of Technical Efficiency

  1999cites this paper
• Geometric shellings of 3-polytopes

  1999cites this paper
• Technical efficiency and distance to a reverse convex set

  1999cites this paper
• Metric Distance Function and Profit: Some Duality Results

  1999cites this paper
• Computational Topology

  1999cites this paper
• Theory and Methodology Technical e ciency and distance to a reverse convex set

  1998cites this paper
• Output-Sensitive Convex Hull Algorithms of Planar Convex Objects

  1998cites this paper
• Shelling Polyhedral 3-Balls and 4-Polytopes

  1998cites this paper
• Riemannian computational geometry: Voronoi diagram delaunay-type triangulation in dually flat space

  1998cites this paper
• Shape space from deformation

  1998cites this paper
• CARVE-a constructive algorithm for real-valued examples

  1998cites this paper
• Parallel Randomized Techniques for Some Fundamental Geometric Problems: A Survey

  1998cites this paper