Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
From MaRDI portal
Publication:3670553
DOI10.1137/0212052zbMath0521.68034OpenAlexW2139594840WikidataQ30053333 ScholiaQ30053333MaRDI QIDQ3670553
Publication date: 1983
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0212052
Analysis of algorithms and problem complexity (68Q25) Quadratic programming (90C20) Linear programming (90C05)
Related Items (only showing first 100 items - show all)
Computing the Smallest T-Shaped Polygon Containing k Points ⋮ Efficient Speed-Up of the Smallest Enclosing Circle Algorithm ⋮ SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS ⋮ Computing the Center of Uncertain Points on Tree Networks ⋮ Distribution-sensitive algorithms ⋮ Structural Properties of Voronoi Diagrams in Facility Location Problems with Continuous Demand ⋮ A Continuous Strategy for Collisionless Gathering ⋮ REPORTING BICHROMATIC SEGMENT INTERSECTIONS FROM POINT SETS ⋮ POINT SET DISTANCE AND ORTHOGONAL RANGE PROBLEMS WITH DEPENDENT GEOMETRIC UNCERTAINTIES ⋮ Filling polyhedral molds ⋮ Computing the smallest k-enclosing circle and related problems ⋮ SUCCESSIVE MAPPINGS: AN APPROACH TO POLYGONAL MESH SIMPLIFICATION WITH GUARANTEED ERROR BOUNDS ⋮ RED-BLUE SEPARABILITY PROBLEMS IN 3D ⋮ The Discrete and Mixed Minimax 2-Center Problem ⋮ Computing the Rectilinear Center of Uncertain Points in the Plane ⋮ THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS ⋮ Inverse stable point problem on trees under an extension of Chebyshev norm and Bottleneck Hamming distance ⋮ A combinatorial bound for linear programming and related problems ⋮ A faster algorithm for the constrained minimum covering circle problem to expedite solving p‐center problems in an irregularly shaped area with holes ⋮ A structured methodology for designing distributed algorithms for mobile entities ⋮ Piercing diametral disks induced by edges of maximum spanning trees ⋮ The minimum covering Euclidean ball of a set of Euclidean balls in \(\mathbb{R}^n\) ⋮ Linear time algorithms for testing approximate congruence in the plane ⋮ Discrete and mixed two-center problems for line segments ⋮ Separating Bichromatic Point Sets by Minimal Triangles with a Fixed Angle ⋮ Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon ⋮ Efficient \(k\)-center algorithms for planar points in convex position ⋮ Computing the center of uncertain points on cactus graphs ⋮ Robustness in the Pareto-solutions for the multi-criteria minisum location problem ⋮ Separating a polyhedron by one translation from a set of obstacles ⋮ VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION ⋮ Explicit Communication Among Stigmergic Robots ⋮ SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS ⋮ On the ‘most normal’ normal ⋮ Linear Time Algorithm for 1-Center in $$\mathfrak {R}^d$$ Under Convex Polyhedral Distance Function ⋮ AnO (n)-algorithm for LP-knapsacks with a fixed number of GUB constraints ⋮ Unnamed Item ⋮ Digital Straightness, Circularity, and Their Applications to Image Analysis ⋮ SEPARABILITY OF POINT SETS BY k-LEVEL LINEAR CLASSIFICATION TREES ⋮ Two-variable linear programming in parallel ⋮ Separating objects in the plane by wedges and strips ⋮ A Modified Kolmogorov–Smirnov Test for Normality ⋮ An optimal online algorithm for halfplane intersection ⋮ Minimum-diameter covering problems ⋮ The backup 2‐center and backup 2‐median problems on trees ⋮ Collection depots facility location problems in trees ⋮ Unnamed Item ⋮ Minimizing the expense transmission time from the source node to demand nodes ⋮ Unnamed Item ⋮ Fuzzy versions of the covering circle problem ⋮ The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots ⋮ Two-variable linear programming in parallel ⋮ Covering convex polygons by two congruent disks ⋮ Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees ⋮ Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions ⋮ Covering uncertain points in a tree ⋮ Dynamic Trees and Dynamic Point Location ⋮ Gathering by Repulsion. ⋮ An O(n log n)-Time Algorithm for the k-Center Problem in Trees ⋮ On the Stretch Factor of Polygonal Chains ⋮ Continuous Center Problems ⋮ Discrete Center Problems ⋮ An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees ⋮ Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model ⋮ TERRAIN VISIBILITY WITH MULTIPLE VIEWPOINTS ⋮ Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees ⋮ COMPUTING A DOUBLE-RAY CENTER FOR A PLANAR POINT SET ⋮ Calculating a minimal sphere containing a polytope defined by a system of linear inequalities ⋮ The geodesic 2-center problem in a simple polygon ⋮ Computing the smallest \(k\)-enclosing circle and related problems ⋮ Computing circular separability ⋮ Extremal polygon containment problems ⋮ Improved algorithms for the bichromatic two-center problem for pairs of points ⋮ Optimal algorithms for some intersection radius problems ⋮ \(k\)-violation linear programming ⋮ A dual algorithm for the minimum covering ball problem in \(\mathbb R^n\) ⋮ Helly-type theorems and generalized linear programming ⋮ Computing a centerpoint of a finite planar set of points in linear time ⋮ Minmax regret 1-facility location on uncertain path networks ⋮ The mixed center location problem ⋮ A primal algorithm for the weighted minimum covering ball problem in \(\mathbb {R}^n\) ⋮ Inverse eccentric vertex problem on networks ⋮ On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ Line search method for solving a non-preemptive strictly periodic scheduling problem ⋮ Geometric complexity of some location problems ⋮ Minimum polygonal separation ⋮ Linear programming in \({\mathbb{R}}^ 3\) and the skeleton and largest incircle of a convex polygon ⋮ A generalization of the concept of distance based on the simplex inequality ⋮ A bird's eye-view of min-max and max-min functionals ⋮ A note on center problems with forbidden polyhedra ⋮ A new O(n\(\cdot \log \,n)\) algorithm for computing the intersection of convex polygons ⋮ On the detection of a common intersection of k convex subjects in the plane ⋮ A linear-time algorithm for linear \(L_ 1\) approximation of points ⋮ On the complexity of polyhedral separability ⋮ Isoperimetric triangular enclosures with a fixed angle ⋮ Minimum-area enclosing triangle with a fixed angle ⋮ Deterministic geoleader election in disoriented anonymous systems ⋮ Minimum enclosing circle of a set of fixed points and a mobile point ⋮ A faster algorithm for 2-cyclic robotic scheduling with a fixed robot route and interval processing times ⋮ The minmax regret gradual covering location problem on a network with incomplete information of demand weights
This page was built for publication: Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
