New lower bounds for convex hull problems in odd dimensions

Keywords

Convex hull, Combinatorics, Mathematics, Omega, Polytope

References

• Lower bounds for algebraic computation treesMichael Ben-Or — 1983
• Lower bounds for linear satisfiability problemsJeff Erickson — 1995
• Arrangements and SpreadsBenjamin W. Grunbaum — 1972
• Lectures on PolytopesGünter M. Ziegler — 1994
• More output-sensitive geometric algorithmsKenneth L. Clarkson — 1994
• A Convex Hull Algorithm Optimal for Point Sets in Even DimensionsRaimund Seidel — 1981
• An Algorithm for Convex PolytopesDonald R. Chand, Sham S. Kapur — 1970
• The Ultimate Planar Convex Hull Algorithm?David Kirkpatrick, Raimund Seidel — 1986
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedraDavid Avis, Komei Fukuda — 1991
• Ray shooting in convex polytopesOtfried Schwarzkopf — 1992
• Derandomizing an Output-sensitive Convex Hull Algorithm in Three DimensionsBernard Chazelle, Jiřı́ Matoušek — 1995
• Two combinatorial problems in the planePaul Erdős, George Purdy — 1995
• Small-dimensional linear programming and convex hulls made easyRaimund Seidel — 1991
• The Complexity of Vertex Enumeration MethodsMartin Dyer — 1983
• Linear Programming in Linear Time When the Dimension Is FixedNimrod Megiddo — 1984
• De functionibus alternantibus earumque divisione per productum e differentiis elementorum conflatum.Carl Gustav Jacob Jacobi — 1841
• On computing Voronoi diagrams by divide-prune-and-conquerNancy M. Amato, Edgar A. Ramos — 1996
• Shadows and slices of polytopesNina Amenta, Günter M. Ziegler — 1996
• An Efficient Algorithm for Determining the Convex Hull of a Finite Planar SetRonald Graham — 1972
• Oriented projective geometryJ. Stolfi — 1987

Cited by

• Lower bounds for linear satisfiability problemsJeff Erickson — 1995
• How many n-vertex triangulations does the 3-sphere have?Eran Nevo, Stedman Wilson — 2013
• Computational aspects of some problems from discrete geometry in higher dimensionsDaniel Werner — 2013
• Lower bounds for fundamental geometric problemsJeffrey Gordon Erickson, Raimund Seidel — 1996
• Algorithms - ESA 2003ESA 2003 Budapest, Di Battista, Giuseppe — 2003
• Weighted geometric set cover problems revisitedSariel Har-Peled, Mira Lee — 2012
• Matching Triangles and Basing Hardness on an Extremely Popular ConjectureAmir Abboud, Virginia Vassilevska Williams, Huacheng Yu — 2015
• On the combinatorial complexity of euclidean Voronoi cells and convex hulls of d-dimensional spheresJean‐Daniel Boissonnat, Menelaos I. Karavelas — 2003
• Efficient detection of motion patterns in spatio-temporal data setsJoachim Gudmundsson, Marc van Kreveld, Bettina Speckmann — 2004
• Convex hulls of spheres and convex hulls of disjoint convex polytopesMenelaos I. Karavelas, Raimund Seidel, Eleni Tzanaki — 2013
• Construction of convex hull classifiers in high dimensionsTetsuji Takahashi, Mineichi Kudo, Atsuyoshi Nakamura — 2011
• Certifying the Restricted Isometry Property is HardAfonso S. Bandeira, Edgar Dobriban, Dustin G. Mixon — 2012
• On the Least Median Square ProblemJeff Erickson, Sariel Har-Peled, David M. Mount — 2004
• Fast Algorithms for Computing the Smallest k-Enclosing CircleSariel Har-Peled, Soham Mazumdar — 2004
• Counting and representing intersections among triangles in three dimensionsEsther Ezra, Micha Sharir — 2004
• Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanesMenelaos I. Karavelas, Eleni Tzanaki — 2009
• An optimal randomized algorithm for maximum Tukey depthTimothy M. Chan — 2004
• Shape fitting with outliersSariel Har-Peled, Yusu Wang — 2003
• Pattern Matching under Polynomial TransformationAyelet Butman, Peter Clifford, Raphaël Clifford — 2011
• On FastMap and the convex hull of multivariate data: toward fast and robust dimension reductionGeorge Ostrouchov, Nagiza F. Samatova — 2005

Related papers

• Convex Hull Problem with Imprecise InputTakayuki Nagai, Seigo Yasutome, Nobuki Tokura — 1996
• Improved algorithm on determining convex hull of 3D point setZheng Liu — 2009
• On an Isomorphic Direction of Improving and Optimizing an Algorithm for Determining the Convex Hull of 2D Point Set or Line Segment SetQi Zhou — 2007
• Generalized Convex Hull Combination ApproachSelcan KOCABAS, Ali Metehan Çalışkan — 2022
• Representation of Bounded Convex Sets By Rational Convex Hull Of Its Gamma-Extreme PointsHoàng Xuân Phú — 1994