On geometric optimization with few violated constraints

DOI10.1007/BF02570713zbMath0844.90071OpenAlexW2010790640MaRDI QIDQ1906043

Ji{ří} Matoušek

Publication date: 2 September 1996

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131409

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (33)

Computing the Smallest T-Shaped Polygon Containing k Points ⋮ Computing a minimum-width square or rectangular annulus with outliers ⋮ Cause I'm a genial imprecise point: outlier detection for uncertain data ⋮ Enclosing \(k\) points in the smallest axis parallel rectangle ⋮ Approximating points by a piecewise linear function ⋮ On the \(k\)-colored rainbow sets in fixed dimensions ⋮ COMPUTING ROUNDNESS IS EASY IF THE SET IS ALMOST ROUND ⋮ Shortest paths in the plane with obstacle violations ⋮ Geometric Applications of Posets ⋮ Covering points by disjoint boxes with outliers ⋮ Removing degeneracy may require unbounded dimension increase ⋮ Clarkson's algorithm for violator spaces ⋮ Robust fitting in computer vision: easy or hard? ⋮ Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon ⋮ Geometric path problems with violations ⋮ Violator spaces: Structure and algorithms ⋮ On enclosing k points by a circle ⋮ A streaming algorithm for 2-center with outliers in high dimensions ⋮ Outlier respecting points approximation ⋮ On approximate range counting and depth ⋮ A sampling-and-discarding approach to chance-constrained optimization: feasibility and Optimality ⋮ Algorithms for Radon partitions with tolerance ⋮ Learning noisy functions via interval models ⋮ Placing Two Axis-Parallel Squares to Maximize the Number of Enclosed Points ⋮ Unnamed Item ⋮ Interval predictor models: identification and reliability ⋮ Computing a Minimum-Width Square or Rectangular Annulus with Outliers ⋮ Robust shape fitting via peeling and grating coresets ⋮ Algorithms for optimal outlier removal ⋮ Geometric applications of posets ⋮ Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation ⋮ Removing degeneracy in LP-type problems revisited ⋮ Computing Shortest Paths in the Plane with Removable Obstacles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On enclosing k points by a circle
• On levels in arrangements and Voronoi diagrams
• A geometric consistency theorem for a symbolic perturbation scheme
• Maintenance of configurations in the plane
• Points and triangles in the plane and halving planes in space
• The densest hemisphere problem
• A bound on local minima of arrangements that implies the upper bound theorem
• Helly-type theorems and generalized linear programming
• Counting triangle crossings and halving planes
• The nature and meaning of perturbations in geometric computing
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• Dynamic half-space range reporting and its applications
• A subexponential bound for linear programming
• Finding k points with minimum diameter and related problems
• The Weighted Euclidean 1-Center Problem
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• On k-Hulls and Related Problems
• Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
• Linear Optimization Queries
• Static and dynamic algorithms for k-point clustering problems
• Computing the smallest k-enclosing circle and related problems
• A combinatorial bound for linear programming and related problems

This page was built for publication: On geometric optimization with few violated constraints