article

Free access

An Algorithm for Convex Polytopes

Authors:

Donald R. Chand,

Sham S. KapurAuthors Info & Claims

Journal of the ACM (JACM), Volume 17, Issue 1

Pages 78 - 86

https://doi.org/10.1145/321556.321564

Published: 01 January 1970 Publication History

PDF eReader

References

[1]

EGGLESTON, H.G. Convexity. Cambridge U. Press, New York and London, 1958.

Google Scholar

[2]

KLEE, V. Convex polytopes and linear programming. Rep. I)1-82-0374, Boeing Scientific Research Labs., Seattle, Wash., 1964.

Google Scholar

[3]

WETS, R. J.-B., AND WITZGALI, C. Towards an algebraic characterization of convex polyhedral cones. Numer. Math. 12 (1968), 134-138.

Digital Library

Google Scholar

Cited By

View all

Tuna HYırtıcı Ö(2024)Investigation of Simple Shape Descriptors for NACA 4 Digit AirfoilsSüleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi10.19113/sdufenbed.1570399Online publication date: 14-Dec-2024
https://doi.org/10.19113/sdufenbed.1570399
Ma ZLi JBai G(2024)ReLU Hull ApproximationProceedings of the ACM on Programming Languages10.1145/36329178:POPL(2260-2287)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632917
Pan YHui XLi JZhu XXu FWang P(2024)A Hybrid Method for Dense Points Enclosing and Observation Planning2024 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC54092.2024.10831790(4868-4874)Online publication date: 6-Oct-2024
https://doi.org/10.1109/SMC54092.2024.10831790
Show More Cited By

Index Terms

An Algorithm for Convex Polytopes
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures

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^@__ __), ...
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 ...
Properties of convex polytopes

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 17, Issue 1

Jan. 1970

195 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321556

Editor:
Gerard Salton
Cornell Univ., Ithaca, NY

Issue’s Table of Contents

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1970

Published in JACM Volume 17, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

227
Total Citations
View Citations
1,920
Total Downloads

Downloads (Last 12 months)174
Downloads (Last 6 weeks)28

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tuna HYırtıcı Ö(2024)Investigation of Simple Shape Descriptors for NACA 4 Digit AirfoilsSüleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi10.19113/sdufenbed.1570399Online publication date: 14-Dec-2024
https://doi.org/10.19113/sdufenbed.1570399
Ma ZLi JBai G(2024)ReLU Hull ApproximationProceedings of the ACM on Programming Languages10.1145/36329178:POPL(2260-2287)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632917
Pan YHui XLi JZhu XXu FWang P(2024)A Hybrid Method for Dense Points Enclosing and Observation Planning2024 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC54092.2024.10831790(4868-4874)Online publication date: 6-Oct-2024
https://doi.org/10.1109/SMC54092.2024.10831790
Choudhary RBarbosa RCabello A(2024)Lifting noncontextuality inequalitiesPhysical Review A10.1103/PhysRevA.109.052216109:5Online publication date: 13-May-2024
https://doi.org/10.1103/PhysRevA.109.052216
Carrasco RFerrada HNavarro CHitschfeld N(2024)An evaluation of GPU filters for accelerating the 2D convex hullJournal of Parallel and Distributed Computing10.1016/j.jpdc.2023.104793184:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2023.104793
Hoang NLinh NPhu H(2024)Octagonal and hexadecagonal cut algorithms for finding the convex hull of finite sets with linear time complexityApplied Mathematics and Computation10.1016/j.amc.2024.128931481(128931)Online publication date: Nov-2024
https://doi.org/10.1016/j.amc.2024.128931
Kieu Linh NHoai Thu V(2023)Regular 2k-Directional Polygon Algorithm for Finding the Convex Hulls of big data sets in 2D2023 RIVF International Conference on Computing and Communication Technologies (RIVF)10.1109/RIVF60135.2023.10471844(372-377)Online publication date: 23-Dec-2023
https://doi.org/10.1109/RIVF60135.2023.10471844
Alvarez-Gonzalez RMendez-Vazquez A(2022)Deep Learning Architecture Reduction for fMRI DataBrain Sciences10.3390/brainsci1202023512:2(235)Online publication date: 8-Feb-2022
https://doi.org/10.3390/brainsci12020235
Assad CMorales GArica J(2022)VERTEX ENUMERATION OF POLYHEDRAPesquisa Operacional10.1590/0101-7438.2022.042.0025457042Online publication date: 2022
https://doi.org/10.1590/0101-7438.2022.042.00254570
Cao ZZhang YTian RMa RHu XColeman SKerr D(2022)Object-Aware SLAM Based on Efficient Quadric Initialization and Joint Data AssociationIEEE Robotics and Automation Letters10.1109/LRA.2022.31906227:4(9802-9809)Online publication date: Oct-2022
https://doi.org/10.1109/LRA.2022.3190622
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

References

Cited By

Index Terms

Recommendations

Convex hulls of spheres and convex hulls of disjoint convex polytopes

Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes

Properties of convex polytopes

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Share

Share this Publication link

Share on social media

Affiliations