On the Complexity of some Basic Problems in Computational Convexity: II. Volume and mixed volumes

No abstract is available for this paper.

• Publication year

  1994

• Venue

  Universität Trier, Mathematik/Informatik, Forschungsbericht

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-94-011-0924-6_17
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Decision Method for Elementary Algebra and Geometry

  2023cited by this paper
• A Source Book

  1995cited by this paper
• A polyhedral method for solving sparse polynomial systems

  1995cited by this paper
• Polytopes and Brunn-Minkowski Theory

  1994cited by this paper
• Successive Determination and Verification of Polytopes by their X-Rays

  1994cited by this paper
• On the complexity of some basic problems in computational convexity: I. Containment problems

  1994cited by this paper
• Homotopies exploiting Newton polytopes for solving sparse polynomial systems

  1994cited by this paper
• Uniform Refinement of a Tetrahedron

  1994cited by this paper
• A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed

  1993cited by this paper
• On the complexity of approximating the maximal inscribed ellipsoid for a polytope

  1993cited by this paper
• CHAPTER 2.9 – Geometric Algorithms

  1993cited by this paper
• Valuations and Dissections

  1993cited by this paper
• CHAPTER 3.2 – Lattice Points

  1993cited by this paper
• CHAPTER 1.2 – Mixed Volumes

  1993cited by this paper
• The union of balls and its dual shape

  1993cited by this paper
• Random Walks in a Convex Body and an Improved Volume Algorithm

  1993cited by this paper
• Oriented Matroids

  1993cited by this paper
• Better lower bounds on detecting affine and spherical degeneracies

  1993cited by this paper
• Minimum-cardinality triangulations of the d-cube for d=5 and d=6

  1993cited by this paper
• Computational complexity of inner and outerj-radii of polytopes in finite-dimensional normed spaces

  1993cited by this paper
• An optimal convex hull algorithm in any fixed dimension

  1993cited by this paper
• Complexity of Polytope Volume Computation

  1993cited by this paper
• Approximating the volume of convex bodies

  1993cited by this paper
• A New Triangulation for Simplicial Algorithms

  1993cited by this paper
• A Monte-Carlo Algorithm for Estimating the Permanent

  1993cited by this paper
• Mathematical Programming and Convex Geometry

  1993cited by this paper
• Computational geometry - an introduction through randomized algorithms

  1993cited by this paper
• Learning an intersection of k halfspaces over a uniform distribution

  1993cited by this paper
• Combinatorial Aspects of Convex Polytopes

  1993cited by this paper
• Product formulas for resultants and Chow forms

  1993cited by this paper
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Basis

  1993cited by this paper
• Handbook of Convex Geometry

  1993cited by this paper
• Random polytopes in a convex polytope, independence of shape, and concentration of vertices

  1993cited by this paper
• Convex Bodies: The Brunn–Minkowski Theory: Minkowski addition

  1993cited by this paper
• A mildly exponential approximation algorithm for the permanent

  1992cited by this paper
• Mixed volumes of polytopes

  1992cited by this paper
• A volume associated with m x n matrices

  1992cited by this paper
• Nonlinear reduction for solving deficient polynomial systems by continuation methods

  1992cited by this paper
• On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part III: Quantifier Elimination

  1992cited by this paper
• Old and New Unsolved Problems in Plane Geometry and Number Theory. By Victor Klee and Stan Wagon

  1992cited by this paper
• Partial Pivoting in Vertex Enumeration

  1992cited by this paper
• The volume of duals and sections of polytopes

  1992cited by this paper
• On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part I: Introduction. Preliminaries. The Geometry of Semi-Algebraic Sets. The Decision Problem for the Existential Theory of the Reals

  1992cited by this paper
• On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part II: The General Decision Problem. Preliminaries for Quantifier Elimination

  1992cited by this paper
• The only convex body with extremal distance from the ball is the simplex

  1992cited by this paper
• Computing the volume, counting integral points, and exponential sums

  1992cited by this paper
• Small-dimensional linear programming and convex hulls made easy

  1991cited by this paper
• Computational geometry column 12

  1991cited by this paper
• An optimal condition for determining the exact number of roots of a polynomial system

  1991cited by this paper
• Sampling and integration of near log-concave functions

  1991cited by this paper
• Old And New Unsolved Problems In Plane Geometry And Number Theory

  1991cited by this paper
• Computing the volume of convex bodies : a case where randomness provably helps

  1991cited by this paper
• On Counting Lattice Points in Polyhedra

  1991cited by this paper
• Problems, problems, problems

  1991cited by this paper
• On the Zone Theorem for Hyperplane Arrangements

  1991cited by this paper
• Polytope volume computation

  1991cited by this paper
• A simple and relatively efficient triangulation of then-cube

  1991cited by this paper
• Counting linear extensions

  1991cited by this paper
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra

  1991cited by this paper
• Unsolved Problems In Geometry

  1991cited by this paper
• The n-dimensional pythagorean theorem

  1990cited by this paper
• A conjecture of Stein on plane dissections

  1990cited by this paper
• Chebyshev polynomials : from approximation theory to algebra and number theory

  1990cited by this paper
• Exterior algebra and projections of polytopes

  1990cited by this paper
• Monotone translation invariant valuations on convex bodies

  1990cited by this paper
• Newton polytopes of the classical resultant and discriminant

  1990cited by this paper
• The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume

  1990cited by this paper
• Equidecomposability and discrepancy; a solution of Tarski's circle-squaring problem

  1990cited by this paper
• Handbook of theoretical computer science - Part A: Algorithms and complexity; Part B: Formal models and semantics

  1990cited by this paper
• Operations research proceedings

  1990cited by this paper
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms

  1990cited by this paper
• New methods in optimization and their industrial uses : state of the art, recent advances, perspectives : proceedings of the symposia held in Pau, October 19-29, 1987 and Paris, November 19, 1987

  1990cited by this paper
• Computational complexity of norm-maximization

  1990cited by this paper
• The extreme projections of the regular simplex

  1990cited by this paper
• Equidissections of polygons

  1990cited by this paper
• On recognizing integer polyhedra

  1990cited by this paper
• On-line and off-line vertex enumeration by adjacency lists

  1990cited by this paper
• The volume of convex bodies and Banach space geometry

  1989cited by this paper
• Handbooks in operations research and management science

  1989cited by this paper
• Hierachical basis preconditioners for second order elliptic problems in three dimensions

  1989cited by this paper
• Elementary Problems: E3301-E3306

  1989cited by this paper
• A random polynomial time algorithm for approximating the volume of convex bodies

  1989cited by this paper
• On the 0-1 Maximization of Positive Definite Quadratic Forms

  1989cited by this paper
• On the complexity of learning from counterexamples

  1989cited by this paper
• The volumes of simplices, or, find the penguin

  1989cited by this paper
• Geometric Algorithms and Combinatorial Optimization

  1988cited by this paper
• Improved Algorithms for Discs and Balls Using Power Diagrams

  1988cited by this paper
• On the Complexity of Computing the Volume of a Polyhedron

  1988cited by this paper
• Points entiers dans les polyèdres convexes

  1988cited by this paper
• Algorithms in Combinatorial Geometry

  1987cited by this paper
• Output-Size Sensitive Algorithms For Constructive Problems In Computational Geometry

  1987cited by this paper
• On the decidability of Diophantine problems in combinatorial geometry

  1987cited by this paper
• Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains

  1987cited by this paper
• An efficient algorithm for obtaining the volume of a special kind of pyramid and application to convex polyhedra

  1986cited by this paper
• Enumerative Combinatorics

  1986cited by this paper
• Hard enumeration problems in geometry and combinatorics

  1986cited by this paper
• Computing the volume is difficult

  1986cited by this paper
• Two formulas for the general multivariate polynomial which interpolates a regular grid on a simplex

  1986cited by this paper
• A geometric inequality and the complexity of computing volume

  1986cited by this paper
• The General Decision Problem

  1986cited by this paper

• Computing the probability of intersection

  2025cites this paper
• Sums of Weighted Lattice Points of Polytopes

  2024cites this paper
• The volume of an isocanted cube is a determinant*

  2024cites this paper
• Equality Cases of the Alexandrov–Fenchel Inequality Are Not in the Polynomial Hierarchy

  2023cites this paper
• EQUALITY CASES OF THE ALEXANDROV–FENCHEL INEQUALITY DO NOT HAVE A POLYNOMIAL DESCRIPTION

  2023cites this paper
• Algebraic Volume for Polytope Arise from Ehrhart Theory

  2023cites this paper
• The Best Ways to Slice a Polytope

  2023cites this paper
• Convex Geometry

  2023cites this paper
• On properties of the set of awards vectors for a claims problem

  2023cites this paper
• Exact Quantization of Multistage Stochastic Linear Problems

  2021cites this paper
• A Proof of the Simplex Mean Width Conjecture

  2021cites this paper
• On the co-NP-completeness of the zonotope containment problem

  2021cites this paper
• An Elementary Proof of the 3 Dimensional Simplex Mean Width Conjecture

  2021cites this paper
• Combinatorial Structure of the Polytope of 2-Additive Measures

  2020cites this paper
• The Polyhedral Structure and Complexity of Multistage Stochastic Linear Problem with General Cost Distribution

  2020cites this paper
• Counting the Number of Solutions to Constraints

  2020cites this paper
• The maximum surface area polytope with 5 vertices inscribed in the sphere $\mathbb{S}^2$

  2020cites this paper
• Quality of Service Ranking by Quantifying Partial Compliance of Requirements

  2020cites this paper
• Minimal witnesses for probabilistic timed automata

  2020cites this paper
• The 4-D Gaussian Random Vector Maximum Conjecture and the 3-D Simplex Mean Width Conjecture

  2020cites this paper
• Average Weights and Power in Weighted Voting Games

  2019cites this paper
• Automatic detection of the support points in relational clustering

  2019cites this paper
• Operational Flexibility in Power Systems — A Geometrical View

  2019cites this paper
• Around the Simplex Mean Width Conjecture

  2018cites this paper
• Volume of Alcoved Polyhedra and Mahler Conjecture

  2018cites this paper
• BOLIB: Bilevel Optimization LIBrary of Test Problems

  2018cites this paper
• Some clustering algorithms in normed planes

  2018cites this paper
• Flag representations of mixed volumes and mixed functionals of convex bodies

  2017cites this paper
• Efficiently counting affine roots of mixed trigonometric polynomial systems

  2017cites this paper
• Mean Width of Regular Polytopes and Expected Maxima of Correlated Gaussian Variables

  2017cites this paper
• Approximating the Volume of Tropical Polytopes is Difficult

  2017cites this paper
• Non-convex Region Description by Hyperplane Arrangements

  2016cites this paper
• Empirical Study of User Preferences Based on Rating Data of Movies

  2016cites this paper
• Multipolar robust optimization

  2016cites this paper
• A note on the relation between joint and differential invariants

  2016cites this paper
• A Semidefinite Hierarchy for Disjointly Constrained Multilinear Programming

  2016cites this paper
• On the Reverse Loomis–Whitney Inequality

  2016cites this paper
• 36 COMPUTATIONAL CONVEXITY

  2016cites this paper
• Mean Width of Regular Polytopes and Expected Maxima of Correlated Gaussian Variables

  2015cites this paper
• A collision detection approach for maximizing the material utilization

  2015cites this paper
• High dimensional population balances for the growth of faceted crystals: Combining Monte Carlo integral estimates and the method of characteristics

  2015cites this paper
• Linear Theory for Self-Localization: Convexity, Barycentric Coordinates, and Cayley–Menger Determinants

  2015cites this paper
• Containment Problems for Projections of Polyhedra and Spectrahedra

  2015cites this paper
• Volume of Hypercubes Clipped by Hyperplanes and Combinatorial Identities

  2015cites this paper
• Crystal Shape Modeling and Convex Geometry - Analysis of Geometric State Spaces

  2015cites this paper
• A collision detection approach for maximizing the material utilization

  2015cites this paper
• Coresets and streaming algorithms for the k-means problem and related clustering objectives

  2014cites this paper
• On The Effect of Hyperedge Weights On Hypergraph Learning

  2014influential citation
• On largest volume simplices and sub-determinants

  2014cites this paper
• Sum of Squares Certificates for Containment of H-Polytopes in V-Polytopes

  2014cites this paper
• On a New Competitive Measure for Oblivious Routing

  2014cites this paper
• Mixed-integer quadratically-constrained programming, piecewise-linear approximation and error analysis with applications in power flow

  2014cites this paper
• A note on the relation between joint and differential invariants

  2014cites this paper
• Root counts of semi-mixed systems, and an application to counting nash equilibria

  2014cites this paper
• Polynomial-Time Amoeba Neighborhood Membership and Faster Localized Solving

  2013cites this paper
• A Semidefinite Hierarchy for Containment of Spectrahedra

  2013cites this paper
• Geometric Analogy and Products of Vectors in n Dimensions

  2013cites this paper
• Fast Subspace Approximation Via Greedy Least-Squares

  2013cites this paper
• El problema del rozamiento en el análisis de estructuras de fábrica mediante modelos de sólidos rígidos

  2013cites this paper
• A novel geometric approach towards a linear theory for sensor localization

  2013cites this paper
• Containment Problems for Polytopes and Spectrahedra

  2012influential citation
• How to solve a semi-infinite optimization problem

  2012cites this paper
• Fast tests for the common causality of time-of-arrival events from their mutual Minkowski distances

  2012cites this paper
• The adaptive convexification algorithm for semi-infinite programming with arbitrary index sets

  2012cites this paper
• Polytopic Discrete-Time Models for Systems with Time-Varying Delays

  2012cites this paper
• RECOVERY OF THE CONFIGURATION OF A SET OF SPACE-TIME EVENTS FROM THEIR MUTUAL MINKOWSKI DISTANCES

  2012cites this paper
• Software for exact integration of polynomials over polyhedra

  2011cites this paper
• Adaptive Algorithms for Semi-Infinite Programming with Arbitrary Index Sets

  2011cites this paper
• Use of the global implicit function theorem to induce singular conditional distributions on surfaces in n dimensions: Part III

  2011cites this paper
• On feasible sets for MPC and their approximations

  2011cites this paper
• Constrained control for time-delay systems.

  2011cites this paper
• Fault tolerant control based on set-theoretic methods

  2011cites this paper
• Explicit Model Predictive Control:Solutions Via Computational Geometry

  2010cites this paper
• On Clustering Bodies: Geometry and Polyhedral Approximation

  2010cites this paper
• No Dimension-Independent Core-Sets for Containment Under Homothetics

  2010cites this paper
• Polyhedra in loop quantum gravity

  2010cites this paper
• Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes

  2009cites this paper
• Mixed volumes, mixed Ehrhart theory and applications to tropical geometry and linkage configurations

  2009cites this paper
• The Successive Projection Algorithm (SPA), an Algorithm with a Spatial Constraint for the Automatic Search of Endmembers in Hyperspectral Data

  2008cites this paper
• Semiparametric Functional Estimation Using Quantile-Based Prior Elicitation

  2008cites this paper
• New algorithms for k-center and extensions

  2008cites this paper
• 1925 – 2007

  2008cites this paper
• Approximating the Radii of Point Sets

  2007cites this paper
• Maximizing the area of an axially symmetric polygon inscribed in a simple polygon

  2007cites this paper
• The Adaptive Convexification Algorithm: A Feasible Point Method for Semi-Infinite Programming

  2007cites this paper
• Efficient Subspace Approximation Algorithms

  2007cites this paper
• Volume Computation Using a Direct Monte Carlo Method

  2007cites this paper
• Polytope ARTMAP: Pattern Classification Without Vigilance Based on General Geometry Categories

  2007cites this paper
• Title: Associate Professor of Information Science

  2007cites this paper
• Measuring Innnite Relations

  2007cites this paper
• H-continuity of fuzzy measures and set defuzzification

  2006influential citation
• A semi-infinite approach to design centering

  2006cites this paper
• Some families of density matrices for which separability is easily tested (10 pages)

  2005cites this paper
• Rigidity and polynomial invariants of convex polytopes

  2005cites this paper
• Computing the Ehrhart quasi-polynomial of a rational simplex

  2005cites this paper
• LARGE TYPICAL CELLS IN POISSON–DELAUNAY MOSAICS DANIEL HUG and ROLF SCHNEIDER Dedicated to Tudor Zamfirescu on the occasion of his sixtieth birthday

  2005cites this paper
• Invariant sets for feedback linearisation based nonlinear predictive control

  2005cites this paper
• Convex Optimization & Euclidean Distance Geometry

  2004cites this paper
• Inner and outer approximations of polytopes using boxes

  2004cites this paper
• A framework to create resource-bounded network services

  2004cites this paper