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
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, The connected \(p\)-center problem on block graphs with forbidden vertices, Separating bichromatic point sets by L-shapes, Improved algorithms for several network location problems with equality measures., Continuous location of dimensional structures., Base station placement on boundary of a convex polygon, An optimal parallel algorithm for linear programming in the plane, Minimum-sum dipolar spanning tree in \(\mathbb R^3\), Constrained minimum enclosing circle with center on a query line segment, Sorting weighted distances with applications to objective function evaluations in single facility location problems., Prune-and-search with limited workspace, Small-dimensional linear programming and convex hulls made easy, Maintaining centdians in a fully dynamic forest with top trees, A note on the minmax regret centdian location on trees, A linear time algorithm for computing minmax regret 1-median on a tree network, A linear algorithm for bisecting a polygon, Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks, One-dimensional \(k\)-center on uncertain data, Finding effective ``Force targets for two-dimensional, multifinger frictional grips, Efficient algorithms for the one-dimensional \(k\)-center problem, New algorithms for mimizing the longest wire length during circuit compaction., Geometric orderings of intersecting translates and their applications, The inverse 1-median problem on a cycle, On Anstreicher's combined phase I-phase II projective algorithm for linear programming, An optimal algorithm for the weighted backup 2-center problem on a tree, The double pivot simplex method, New algorithms for facility location problems on the real line, Two scheduling problems with fuzzy due-dates, Algorithms for weak and wide separation of sets, A recursive algorithm for finding the minimum covering sphere of a polytope and the minimum covering concentric spheres of several polytopes, Computing the center of uncertain points on tree networks, The slab dividing approach to solve the Euclidean \(P\)-center problem, Stabbing isothetic boxes and rectangles in \(O(n\log n)\) time, Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under \(l_ \infty\)-distance, Seven fingers allow force-torque closure grasps on any convex polyhedron, Fast computation of smallest enclosing circle with center on a query line segment, Improved bounds on the average distance to the Fermat-Weber center of a convex object, Cooperative TSP, Computing the geodesic center of a simple polygon, Optimal deterministic algorithms for 2-d and 3-d shallow cuttings, Measure of circularity for parts of digital boundaries and its fast computation, A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case, Center location problems on tree graphs with subtree-shaped customers, A fast algorithm for the alpha-connected two-center decision problem, A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane, On the ball spanned by balls, A simple algorithm for computing the smallest enclosing circle, Computing shortest transversals, On weighted rectilinear 2-center and 3-center problems, K-center and K-median problems in graded distances, Up- and downgrading the 1-center in a network, Generalized \(p\)-center problems: Complexity results and approximation algorithms, A linear programming approach to highly precise clock synchronization over a packet network, Locational optimization problems solved through Voronoi diagrams, Optimal algorithms for the path/tree-shaped facility location problems in trees, Algorithms for the robust 1-center problem on a tree, Special issue on Locational analysis, Location of rectilinear center trajectories, Geometric methods to solve max-ordering location problems, Restricted center problems under polyhedral gauges, A note on the location of an obnoxious facility on a network, A geometrical solution for quadratic bicriteria location models, A comment on a minmax location problem, Locating service centers with precedence constraints, The complexity of finding minimal Voronoi covers with applications to machine learning, A deep cut ellipsoid algorithm for convex programming: Theory and applications, A sweepline algorithm to solve the two-center problem, Using enclosing ellipsoids in multiaxial fatigue strength criteria, Separability of imprecise points, The searching over separators strategy to solve some NP-hard problems in subexponential time, Splitting a configuration in a simplex, Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces, An efficient algorithm for the smallest enclosing ball problem in high dimensions, Competitive facility location: the Voronoi game, Separability by two lines and by nearly straight polygonal chains, A new bound and an \(O(mn)\) algorithm for the undesirable 1-median problem (maxian) on networks, Efficient algorithms for center problems in cactus networks, Fuzzy disk for covering fuzzy points, An efficient inexact Newton-CG algorithm for the smallest enclosing ball problem of large dimensions, Dynamic half-space range reporting and its applications, A mixed breadth-depth first strategy for the branch and bound tree of Euclidean \(k\)-center problems, Optimal separable partitioning in the plane, The (1|1)-Centroid Problem in the Plane with Distance Constraints, Rearranging a sequence of points onto a line, On the planar piecewise quadratic 1-center problem, Optimal conditions for connectedness of discretized sets, Efficient piecewise-linear function approximation using the uniform metric, Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming, An efficient algorithm for the proximity connected two center problem, Extensive facility location problems on networks: an updated review, Point location in zones of \(k\)-flats in arrangements, About the decidability of polyhedral separability in the lattice \(\mathbb {Z}^d\). Recognizing digital polyhedra with a prescribed number of faces, Bipartite diameter and other measures under translation, Solution of an equiweighted minimax location problem on a hemisphere, \(\varepsilon\)-approximation minimization of convex functions in fixed dimension, \(\alpha\)-kernel problem with fuzzy visibility, A subexponential bound for linear programming, Linear-time fitting of a \(k\)-step function, Linear time algorithms for Euclidean 1-center in \(\mathfrak {R}^d\) with non-linear convex constraints, The multi-service center problem, Determining digital circularity using integer intervals, New approaches to the robust 1-center location problems on tree networks, Asynchronous arbitrary pattern formation: the effects of a rigorous approach, Constant work-space algorithms for facility location problems, Geometric p-Center Problems with Centers Constrained to Two Lines, The Mixed Center Location Problem, Efficient algorithms for computing one or two discrete centers hitting a set of line segments, The discrete and mixed minimax 2-center problems, Dynamic minimum bichromatic separating circle, A dual algorithm for the minimum covering weighted ball problem in \({\mathbb{R}^n}\), The \(p\)-center problem under locational uncertainty of demand points, Some variations on constrained minimum enclosing circle problem, Strict \(L_{\infty }\) isotonic regression, Variations of largest rectangle recognition amidst a bichromatic point set, The connected disk covering problem, Separating bichromatic point sets in the plane by restricted orientation convex hulls, Self-stabilizing gathering of mobile robots under crash or Byzantine faults, Gathering by repulsion, Computation of inverse 1-center location problem on the weighted trapezoid graphs, \(k\)-balanced center location problem: a new multi-objective facility location problem, A continuous strategy for collisionless gathering, Fuzzy facility location problem with preference of candidate sites, THE ALIGNED K-CENTER PROBLEM, Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares, A linear time algorithm for the robust recoverable selection problem, Optimizing squares covering a set of points, Robust location problems with pos/neg weights on a tree, CONSTRAINED OPTIMAL LOCATION, An optimal randomized algorithm for \(d\)-variate zonoid depth, Adaptive shape diagrams for multiscale morphometrical image analysis, Fast circular arc segmentation based on approximate circularity and cuboid graph, Rectilinear m -Center problem, Bichromatic 2-center of pairs of points, Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets, Largest bounding box, smallest diameter, and related problems on imprecise points, Efficient algorithms for the smallest enclosing ball problem, Chebyshev center of the intersection of balls: complexity, relaxation and approximation, Linear updates for a single-phase projective method, Inverse group 1-median problem on trees, An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem, Linear-Time Fitting of a k-Step Function, Linear Time Algorithms for Euclidean 1-Center in $$\mathfrak {R}^d$$ with Non-linear Convex Constraints, A note on computing the center of uncertain data on the real line, Voronoi diagrams for a moderate-sized point-set in a simple polygon, Constructing the convex hull of a partially sorted set of points, On the recognition of digital circles in linear time, Group centre and group median of a tree, Minimum Enclosing Circle of a Set of Fixed Points and a Mobile Point, Solution methods for a min-max facility location problem with regional customers considering closest Euclidean distances, Computing the Line-Constrained k-center in the Plane for Small k, Congruence, similarity, and symmetries of geometric objects, Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, A randomized algorithm for fixed-dimensional linear programming, On computing the closest boundary point on the convex hull, An elementary algorithm for digital arc segmentation, Rendezvous in planar environments with obstacles and unknown initial distance, The weighted \(k\)-center problem in trees for fixed \(k\), A combinatorial algorithm for the ordered 1-median problem on cactus graphs, Computing a geodesic two-center of points in a simple polygon, \(L_1\) geodesic farthest neighbors in a simple polygon and related problems, Combinatorial algorithms for the uniform-cost inverse 1-center problem on weighted trees, Efficient algorithm for transversal of disjoint convex polygons., Transversal of disjoint convex polygons., Isoperimetric enclosures, On the planar two-center problem and circular hulls, Isotonic regression for multiple independent variables, Monochromatic geometric \(k\)-factors for bicolored point sets with auxiliary points, The generalized trust region subproblem: solution complexity and convex hull results, 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, 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
