Article

Free access

Linear programming and convex hulls made easy

Author:

Raimund SeidelAuthors Info & Claims

SCG '90: Proceedings of the sixth annual symposium on Computational geometry

Pages 211 - 215

https://doi.org/10.1145/98524.98570

Published: 01 May 1990 Publication History

Abstract

We present two randomized algorithms. One solves linear programs involving m constraints in d variables in expected time Ο(m). The other constructs convex hulls of n points in R^d, d > 3, in expected time Ο(n^⌈d/2⌉). In both bounds d is considered to be a constant. In the linear programming algorithm the dependence of the time bound on d is of the form d!. The main virtue of our results lies in the utter simplicity of the algorithms as well as their analyses.

References

[1]

D.tL Chand and S.S. Kapur, An Algorithm for Convex Polytopes, JA CM 17 (1970) 78-86.

Digital Library

[2]

K.L. Clarkson, Linear Programming in O(n3d~) Time, Inf. Proe. Letters ~2 (1986) 21-2J.

Digital Library

[3]

K.L. Clarkson, Las Vegas Algorithms for Linear and Integer Programming When the Dimension is Small, Manuscript, (Oct. 1989).

[4]

K.L. Clarkson and P.W. Shot, Applications of Random Sampling in Computational Geometry II, Discrete eJ Computational Geometry 4 (1989) 387- 422.

Digital Library

[5]

M.E. Dyer, Linear Algorithms for Two and Three- Variable Linear Programs, SIAM J. on Computing s (i 9s~) 3~-45.

[6]

M.E. Dyer and A.M. Frieze, A Randomized Algorithm for Fixed-Dimensional Linear Programming, Manuscript (I 987).

[7]

H. Edelsbrunner, Algorithms in Combinatorial Ge. ometry, Springer-Verlag (1987).

Digital Library

[8]

R.L. Graham, An Efficient Algorithm for Construeting the Convex Hull of a Finite Planar Set, Inf. Proc. Letters 1 (1972) 13g-133.

[9]

M. Kallay, Convex Hull Algorihms in Higher Dimensions, Manuscript (1981).

[10]

N. Megiddo, Linear-Time Algorithms for Linear Programming in R3 and Related Problems, SIAM J. on Computing 12 (1983) 759-776.

[11]

N. Megiddo, Linear Programming in Linear Time when the Dimension is Fixed, Journal of the A CM 31 (~9s4) ~4-~27.

Digital Library

[12]

F.P. Preparata and S.J. Hong, Convex Hulls of Finite Point Sets in Two and Three Dimensions, Comm. of the A CM 20 (1977) 87-93.

Digital Library

[13]

R. Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, Univ. ob British Columbia, Dept. of Comp. Sci. Tech. Rep. 81-14 (1981).

Digital Library

[14]

It. Seidel, Constructing Higher-Dimensional Convex Hulls at Logarithmic Cost per Face, Proe. 18th A CM STOC (19863 4o4-413.

Digital Library

[15]

G. Swart, Finding the Convex Hull Facet by Facet, Journal of Algorithms 6 (1985) 17-48.

Cited By

Aanjaneya MNagarakatte S(2024)Maximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear Programs with Convex Hull as the Intermediate RepresentationProceedings of the ACM on Programming Languages10.1145/36564278:PLDI(1239-1263)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656427
Uddin RMahin MRajan PRavishankar CTsotras V(2023)Dwell Regions: Generalized Stay Regions for Streaming and Archival Trajectory DataACM Transactions on Spatial Algorithms and Systems10.1145/35438509:2(1-35)Online publication date: 12-Apr-2023
https://dl.acm.org/doi/10.1145/3543850
Abo-Alsabeh RSalhi A(2020)An Evolutionary Approach to Constructing the Minimum Volume Ellipsoid Containing a Set of Points and the Maximum Volume Ellipsoid Embedded in a Set of PointsJournal of Physics: Conference Series10.1088/1742-6596/1530/1/0120871530(012087)Online publication date: 27-May-2020
https://doi.org/10.1088/1742-6596/1530/1/012087
Show More Cited By

Index Terms

Linear programming and convex hulls made easy
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
  2. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Convex hulls of spheres and convex hulls of disjoint convex polytopes

Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@__ __"1"=<"i"<>"j"=<"mn"in"j^@__ __^d^2^@__ __), ...
Small-dimensional linear programming and convex hulls made easy

We present two randomized algorithms. One solves linear programs involvingm constraints ind variables in expected timeO(m). The other constructs convex hulls ofn points in d,d>3, in expected timeO(n[d/2]). In both boundsd is considered to be a constant. ...
Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

Given a set Σ of spheres in E^d, with d≥3 and d odd, having a fixed number of m distinct radii ρ₁,ρ₂,...,ρ_m, we show that the worst-case combinatorial complexity of the convex hull CH_d(Σ) of Σ is Θ(Σ_{{1≤i≠j≤m}}n_in_j^{⌊ d/2 ⌋}), where n_i is the number of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '90: Proceedings of the sixth annual symposium on Computational geometry

May 1990

371 pages

ISBN:0897913620

DOI:10.1145/98524

Chairman:
Raimund Seidel

Copyright © 1990 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SOCG

Sponsor:

SOCG: 6th Annual Conference on Computational Geometry

June 7 - 9, 1990

California, Berkley, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

106
Total Citations
View Citations
526
Total Downloads

Downloads (Last 12 months)149
Downloads (Last 6 weeks)37

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Aanjaneya MNagarakatte S(2024)Maximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear Programs with Convex Hull as the Intermediate RepresentationProceedings of the ACM on Programming Languages10.1145/36564278:PLDI(1239-1263)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656427
Uddin RMahin MRajan PRavishankar CTsotras V(2023)Dwell Regions: Generalized Stay Regions for Streaming and Archival Trajectory DataACM Transactions on Spatial Algorithms and Systems10.1145/35438509:2(1-35)Online publication date: 12-Apr-2023
https://dl.acm.org/doi/10.1145/3543850
Abo-Alsabeh RSalhi A(2020)An Evolutionary Approach to Constructing the Minimum Volume Ellipsoid Containing a Set of Points and the Maximum Volume Ellipsoid Embedded in a Set of PointsJournal of Physics: Conference Series10.1088/1742-6596/1530/1/0120871530(012087)Online publication date: 27-May-2020
https://doi.org/10.1088/1742-6596/1530/1/012087
Kim YLin MManocha D(2018)Collision DetectionHumanoid Robotics: A Reference10.1007/978-94-007-6046-2_26(1933-1956)Online publication date: 10-Oct-2018
https://doi.org/10.1007/978-94-007-6046-2_26
Liu SChen G(2018)Force Feedback and Haptic RenderingDynamics and Control of Robotic Manipulators with Contact and Friction10.1002/9781119422518.ch5(175-223)Online publication date: 19-Nov-2018
https://doi.org/10.1002/9781119422518.ch5
Kim YLin MManocha D(2017)Collision DetectionHumanoid Robotics: A Reference10.1007/978-94-007-7194-9_26-1(1-24)Online publication date: 27-Jul-2017
https://doi.org/10.1007/978-94-007-7194-9_26-1
Teng S(2016)Scalable Algorithms for Data and Network AnalysisFoundations and Trends® in Theoretical Computer Science10.1561/040000005112:1–2(1-274)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1561/0400000051
Sirigina RMadhukumar A(2016)Full-Duplex Decode-and-Forward Relay-Assisted Interference Management: A Diversity Gain Region PerspectiveIEEE Transactions on Communications10.1109/TCOMM.2015.250259864:1(141-152)Online publication date: Jan-2016
https://doi.org/10.1109/TCOMM.2015.2502598
Ennen PEwert DSchilberg DJeschke S(2016)Efficient Collision Avoidance for Industrial Manipulators with Overlapping WorkspacesAutomation, Communication and Cybernetics in Science and Engineering 2015/201610.1007/978-3-319-42620-4_38(479-489)Online publication date: 29-Oct-2016
https://doi.org/10.1007/978-3-319-42620-4_38
Giese ALatypov DAmato N(2014)Reciprocally-Rotating Velocity Obstacles2014 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA.2014.6907324(3234-3241)Online publication date: May-2014
https://doi.org/10.1109/ICRA.2014.6907324
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten