Low-dimensional linear programming with violations

No abstract is available for this paper.

• Publication year

  2002

• Venue

  The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.

• Publication date

  2002-11-16

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/SFCS.2002.1181981
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Slowing down sorting networks to obtain faster sorting algorithms

  2015cited by this paper
• Fast Algorithms for Computing the Smallest k-Enclosing Disc

  2003cited by this paper
• K-Levels of Concave Surfaces

  2002cited by this paper
• Dynamic planar convex hull

  2002cited by this paper
• Notes on computing peaks in k-levels and parametric spanning trees

  2001cited by this paper
• An Improved Bound for k-Sets in Three Dimensions

  2000cited by this paper
• Lovasz's lemma for the three-dimensional K-level of concave surfaces and its applications

  1999cited by this paper
• Remarks on k-Level Algorithms in the Plane

  1999cited by this paper
• Taking a walk in a planar arrangement

  1999cited by this paper
• Dynamic planar convex hull operations in near-logarithmic amortized time

  1999cited by this paper
• On range reporting, ray shooting and k-level construction

  1999cited by this paper
• Efficient algorithms for geometric optimization

  1998cited by this paper
• Improved Bounds for Planar k -Sets and Related Problems

  1998cited by this paper
• On the Approximability of Minimizing Nonzero Variables or Unsatisfied Relations in Linear Systems

  1998cited by this paper
• On levels in arrangements of lines

  1998cited by this paper
• Random sampling, halfspace range reporting, and construction of (/spl les/k)-levels in three dimensions

  1998cited by this paper
• Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions.

  1998cited by this paper
• On enumerating and selecting distances

  1998cited by this paper
• Geometric Applications of a Randomized Optimization Technique

  1998cited by this paper
• Data structures for mobile data

  1997cited by this paper
• On Levels in Arrangements of Lines, Segments, Planes, and Triangles%

  1997cited by this paper
• Deterministic algorithms for 2-d convex programming and 3-d online linear programming

  1997cited by this paper
• Improved bounds on planar k-sets and k-levels

  1997cited by this paper
• New lower bounds for convex hull problems in odd dimensions

  1996cited by this paper
• Fixed-dimensional linear programming queries made easy

  1996cited by this paper
• AN OPTIMAL ALGORITHM FOR COMPUTING (≤K)-LEVELS, WITH APPLICATIONS

  1996cited by this paper
• Las Vegas algorithms for linear and integer programming when the dimension is small

  1995cited by this paper
• The Complexity and Approximability of Finding Maximum Feasible Subsystems of Linear Relations

  1995cited by this paper
• On Enclosing k Points by a Circle

  1995cited by this paper
• Output-sensitive results on convex hulls, extreme points, and related problems

  1995cited by this paper
• A compendium of NP optimization problems

  1994cited by this paper
• k-Violation Linear Programming

  1994cited by this paper
• On geometric optimization with few violated constraints

  1994influential reference
• Constructing levels in arrangements and higher order Voronoi diagrams

  1994cited by this paper
• Cutting hyperplanes for divide-and-conquer

  1993cited by this paper
• Computing the Smallest K-enclosing Circle and Related Problems

  1993cited by this paper
• Static and Dynamic Algorithms for k-Point Clustering Problems

  1993cited by this paper
• A bound on local minima of arrangements that implies the upper bound theorem

  1993cited by this paper
• Dehn-Sommerville relations, upper bound theorem, and levels in arrangements

  1993cited by this paper
• An optimal algorithm for the (≤ k)-levels, with applications to separation and transversal problems

  1993cited by this paper
• Finding Maximally Consistent Sets of Halfspaces

  1993cited by this paper
• Reporting Points in Halfspaces

  1992cited by this paper
• A Combinatorial Bound for Linear Programming and Related Problems

  1992cited by this paper
• A general approach to removing degeneracies

  1991cited by this paper
• Small-dimensional linear programming and convex hulls made easy

  1991cited by this paper
• Dynamic three-dimensional linear programming

  1991cited by this paper
• Onk-sets in arrangements of curves and surfaces

  1991influential reference
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms

  1990cited by this paper
• Determining the Separation of Preprocessed Polyhedra - A Unified Approach

  1990cited by this paper
• Output sensitive construction of levels and Voronoi diagrams in Rd of order 1 to k

  1990cited by this paper
• Applications of random sampling in computational geometry, II

  1988cited by this paper
• On the Detection of a Common Intersection of k Convex Polyhedra

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

  1987cited by this paper
• Intersection of convex objects in two and three dimensions

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

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

  1984cited by this paper
• On the Number of k-Subsets of a Set of n Points in the Plane

  1984cited by this paper
• Linear Time Algorithms for Two- and Three-Variable Linear Programs

  1984cited by this paper
• The power of geometric duality

  1983cited by this paper
• Fast Detection of Polyhedral Intersection

  1983cited by this paper
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems

  1982cited by this paper
• Linear-time algorithms for linear programming in R3 and related problems

  1982cited by this paper
• Maintenance of Configurations in the Plane

  1981cited by this paper
• Applying parallel computation algorithms in the design of serial algorithms

  1981cited by this paper
• Algorithmic graph theory and perfect graphs

  1980cited by this paper

• Robust Bichromatic Classification in 3D Using Planes and Slices

  2025cites this paper
• On computing the maximum-volume bichromatic separating box

  2025cites this paper
• Robust Classification of Dynamic Bichromatic point Sets in R2

  2024influential citation
• Robust Bichromatic Classification using Two Lines

  2024influential citation
• Generic Techniques for Building Top-k Structures

  2022cites this paper
• Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices

  2021cites this paper
• Algorithms for Radon Partitions with Tolerance

  2020cites this paper
• Improved Algorithm for Computing the Maximum-volume Bichromatic Separating Box

  2020cites this paper
• Shortest Paths in the Plane with Obstacle Violations

  2020cites this paper
• Approximation algorithms for the covering-type k-violation linear program

  2019cites this paper
• Linear Programming in Low Dimensions

  2019cites this paper
• Computing Shortest Paths in the Plane with Removable Obstacles

  2018cites this paper
• Geometric Path Problems with Violations

  2018cites this paper
• Data structures for analyzing geometric data

  2017cites this paper
• 49 LINEAR PROGRAMMING

  2017cites this paper
• Nearest-Neighbor Searching Under Uncertainty I

  2017cites this paper
• Approximating the $k$-Level in Three-Dimensional Plane Arrangements

  2016influential citation
• 50 LINEAR PROGRAMMING

  2016cites this paper
• Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications

  2016cites this paper
• Dynamic Minimum Bichromatic Separating Circle

  2015cites this paper
• Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings

  2015cites this paper
• Geometric Computing over Uncertain Data

  2015cites this paper
• 2 Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings 1 . 1 Standard Cuttings

  2015cites this paper
• Geometric Optimization in some Proximity and Bioinformatics Problems

  2014influential citation
• Covering Linear Programming with Violations

  2014cites this paper
• Separability of imprecise points

  2014cites this paper
• On the coarseness of bicolored point sets

  2013cites this paper
• Absolute approximation of Tukey depth: Theory and experiments

  2013influential citation
• Covering a bichromatic point set with two disjoint monochromatic disks

  2013cites this paper
• Algorithms for Data Depth

  2013influential citation
• Geometric Optimization for Classification Problems.

  2013influential citation
• Approximation Algorithms for Geometric Covering Problems for Disks and Squares

  2013cites this paper
• Probabilistic covering problems

  2013cites this paper
• Approximating Points by a Piecewise Linear Function

  2013cites this paper
• Minimizing the error of linear separators on linearly inseparable data

  2012influential citation
• Linear programming in low dimensions

  2011cites this paper
• RANGE SEARCHING DATA STRUCTURES WITH CACHE LOCALITY

  2011cites this paper
• Outlier Respecting Points Approximation

  2011cites this paper
• On the bichromatic k-set problem

  2010influential citation
• Selection of Best Outlier Detection Method Using Regression Analysis

  2010cites this paper
• Thin partitions: isoperimetric inequalities and a sampling algorithm for star shaped bodies

  2010cites this paper
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries

  2010cites this paper
• Minimum separating circle for bichromatic points by linear programming

  2010cites this paper
• Approximating Points by a Piecewise Linear Function: II. Dealing with Outliers

  2009cites this paper
• Chapter 11 Linear programming in Low Dimensions

  2009cites this paper
• Measuring the error of linear separators on linearly inseparable data

  2009cites this paper
• Bounds for point recolouring in geometric graphs

  2009cites this paper
• Enclosing weighted points with an almost-unit ball

  2009cites this paper
• Approximating Points by a Piecewise Linear Function

  2009cites this paper
• Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families

  2009cites this paper
• Problems on Geometric Graphs with Applications to Wireless Networks

  2009cites this paper
• Coloring Geometric Range Spaces

  2009cites this paper
• Algorithms for optimal outlier removal

  2009cites this paper
• A general approach for cache-oblivious range reporting and approximate range counting

  2009cites this paper
• Covering Points by Disjoint Boxes with Outliers

  2009cites this paper
• Delineating Boundaries for Imprecise Regions

  2008cites this paper
• An Efficient Algorithm for Euclidian 2-Center with Outliers ∗

  2008influential citation
• On the Complexity of Point Recolouring in Geometric Graphs

  2008cites this paper
• On Geometric Range Searching, Approximate Counting and Depth Problems

  2008influential citation
• Output-sensitive algorithms for Tukey depth and related problems

  2008cites this paper
• On the bichromatic k-set problem

  2008cites this paper
• An Efficient Algorithm for 2D Euclidean 2-Center with Outliers

  2008cites this paper
• An optimal randomized algorithm for d-variate zonoid depth

  2008cites this paper
• k-Sets and k-Facets

  2007cites this paper
• On Approximate Range Counting and Depth

  2007cites this paper
• Bichromatic Discrepancy via Convex Partitions

  2006cites this paper
• A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries

  2006cites this paper
• Robust Shape Fitting via Peeling and Grating Coresets

  2006cites this paper
• On a Geometric Generalization of the Upper Bound Theorem

  2006cites this paper
• Tight Bounds for Point Recolouring

  2006cites this paper
• On approximating the depth and related problems

  2005influential citation
• Delineating boundaries for imprecise regions

  2005cites this paper
• Separability with Outliers

  2005influential citation
• Computing the Least Median of Squares Estimator in Time O(nd)

  2005influential citation
• Fast Algorithms for Computing the Smallest k-Enclosing Circle

  2004cites this paper
• On the Least Median Square Problem

  2004cites this paper
• An optimal randomized algorithm for maximum Tukey depth

  2004cites this paper
• Algorithms - ESA 2003

  2003influential citation
• On the Least Median Square Problem

  2003cites this paper
• On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences

  2003cites this paper
• Shape fitting with outliers

  2003cites this paper
• MIT Open Access Articles Covering points by disjoint boxes with outliers

  year unknowncites this paper