High-Dimensional Shape Fitting in Linear Time

No abstract is available for this paper.

• Publication year

  2003

• Venue

  SCG '03

• Publication date

  2003-06-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/777792.777799
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

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

  2025cited by this paper
• Approximate minimum enclosing balls in high dimensions using core-sets

  2003cited by this paper
• An Improved Algorithm for Approximating the Radii of Point Sets

  2003cited by this paper
• Smaller core-sets for balls

  2003cited by this paper
• Approximate clustering via core-sets

  2002cited by this paper
• Geometric Optimization Problems Likely Not Contained in APX

  2002cited by this paper
• Projective clustering in high dimensions using core-sets

  2002influential reference
• On approximating the radii of point sets in high dimensions

  2002cited by this paper
• Lectures on discrete geometry

  2002cited by this paper
• Approximate shape fitting via linearization

  2001cited by this paper
• On maximization of quadratic form over intersection of ellipsoids with common center

  1999cited by this paper
• Global quadratic optimization via conic relaxation

  1998influential reference
• Note on the computational complexity ofj-radii of polytopes in ℝn

  1996cited by this paper
• On the complexity of some basic problems in computational convexity: I. Containment problems

  1994cited by this paper
• Computational complexity of inner and outerj-radii of polytopes in finite-dimensional normed spaces

  1993influential reference
• Computational complexity of norm-maximization

  1990cited by this paper
• On the Complexity of Some Geometric Problems in Unbounded Dimension

  1990cited by this paper
• Algorithms in Combinatorial Geometry

  1987cited by this paper

• Relational Approximations for Subspace Primitives

  2025cites this paper
• Root Ridge Leverage Score Sampling for ℓp Subspace Approximation

  2024cites this paper
• Sublinear Time Algorithms for Several Geometric Optimization (With Outliers) Problems In Machine Learning

  2023influential citation
• Conic Linear Programming

  2021cites this paper
• A Sub-linear Time Framework for Geometric Optimization with Outliers in High Dimensions

  2020cites this paper
• Coresets for Gaussian Mixture Models of Any Shape

  2019cites this paper
• NSF Proposal: AF 7435149: Towards better geometric algorithms: Summarizing, partitioning and shrinking data

  2018cites this paper
• 48 CORESETS AND SKETCHES

  2017cites this paper
• Training Mixture Models at Scale via Coresets

  2017cites this paper
• Training Gaussian Mixture Models at Scale via Coresets

  2017cites this paper
• Coresets and Sketches

  2016cites this paper
• Private k-means clustering : algorithms and applications

  2016cites this paper
• Sparse Approximation via Generating Point Sets

  2015cites this paper
• Community Sense and Response Systems

  2014cites this paper
• Spectral Approaches to Nearest Neighbor Search

  2014cites this paper
• Approximation and Streaming Algorithms for Projective Clustering via Random Projections

  2014cites this paper
• Low Rank Matrix Approximation in Linear Time

  2014cites this paper
• K-robots clustering of moving sensors using coresets

  2013cites this paper
• A near-linear algorithm for projective clustering integer points

  2012cites this paper
• PlanetData Network of Excellence FP 7 – 257641 D 1 . 5 Trend and anomaly detection in non-structured data Coordinator :

  2012cites this paper
• Linear Time Algorithm for Projective Clustering

  2012cites this paper
• Fitting Flats to Points with Outliers

  2011cites this paper
• Scalable Training of Mixture Models via Coresets

  2011cites this paper
• Coresets and their applications

  2010cites this paper
• Private coresets

  2009cites this paper
• Modeling and Optimization of Correction Measures for Human Extremities

  2008influential citation
• Efficient Subspace Approximation Algorithms

  2007influential citation
• Sampling-based dimension reduction for subspace approximation

  2007cites this paper
• Approximating the Radii of Point Sets

  2007cites this paper
• Smallest Enclosing Ball for a Point Set with Strictly Convex Level Sets

  2007cites this paper
• Sampling-based algorithms for dimension reduction

  2007cites this paper
• Geometric Approximation via Coresets

  2007cites this paper
• Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope

  2006cites this paper
• Exact analysis of optimal configurations in radii computations

  2005cites this paper
• Extremal point queries with lines and line segments and related problems

  2005cites this paper
• Separability with Outliers

  2005cites this paper
• Approximating the Radii of Point Sets ∗

  2005cites this paper
• Minimum Enclosing Polytope in High Dimensions

  2004cites this paper
• No, Coreset, No Cry

  2004cites this paper
• Faster core-set constructions and data stream algorithms in fixed dimensions

  2004cites this paper
• Transformations and algorithms for least sum of squares hypersphere fitting

  2004cites this paper
• Radii minimal projections of polytopes and constrained optimization of symmetric polynomials

  2003cites this paper
• An Improved Algorithm for Approximating the Radii of Point Sets

  2003cites this paper
• A Coordinate System associated to a Point Cloud issued from a Manifold: Definition, Properties and Applications. (Un système de coordonnées associé à un échantillon de points d'une variété: définition, propriétés et applications)

  2003cites this paper
• Faster Core-Set Constructions and Data Stream Algorithms in Fixed Dimensions

  2003cites this paper