Practical methods for shape fitting and kinetic data structures using coresets

DOI10.1007/s00453-007-9067-9zbMath1163.68042MaRDI QIDQ1006384

Kasturi R. Varadarajan, Raghunath Poreddy, Pankaj K. Agarwal, Hai Yu

Publication date: 24 March 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9067-9

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68P05: Data structures

Related Items

Unnamed Item, Unnamed Item, Robust shape fitting via peeling and grating coresets, Dynamic coresets, No dimension-independent core-sets for containment under homothetics, A strong coreset algorithm to accelerate OPF as a graph-based machine learning in large-scale problems, Monte Carlo maximum likelihood circle fitting using circular density functions

Uses Software

• Miniball
• ANN

Cites Work

• Unnamed Item
• Unnamed Item
• Minimum-volume enclosing ellipsoids and core sets
• Approximation algorithms for a \(k\)-line center
• Smaller coresets for \(k\)-median and \(k\)-means clustering
• Line transversals of balls and smallest enclosing cylinders in three dimensions
• Approximation algorithms for minimum-width annuli and shells
• Applications of random sampling in computational geometry. II
• Faster core-set constructions and data-stream algorithms in fixed dimensions
• Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions
• Approximating extent measures of points
• Algorithms for a Minimum Volume Enclosing Simplex in Three Dimensions
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• A Linear Programming Approach to the Cutting-Stock Problem
• Space-time tradeoffs for approximate nearest neighbor searching
• Approximate clustering via core-sets
• Space-efficient approximate Voronoi diagrams
• On coresets for k-means and k-median clustering
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Data Structures for Mobile Data
• Las Vegas algorithms for linear and integer programming when the dimension is small
• Shape Fitting with Outliers
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
• A Subexponential Algorithm for Abstract Optimization Problems
• A practical approach for computing the diameter of a point set
• Approximate minimum enclosing balls in high dimensions using core-sets
• Exact and approximation algorithms for minimum-width cylindrical shells
• Maintaining the extent of a moving point set