Skip to main content

Questions tagged [simplex]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer

Why is infeasibility of linear programming considered to be an NP problem?

I recently came across this question, and the way I think people usually go about this is to find a certificate that answers 'yes' to the decision problem 'Is this LP infeasible?' Or, given a ...
Namrata Banerji's user avatar
2 votes
1 answer

Sort array of 3D points to maximize number of tetrahedra in the array

Let $P$ be a indexable set(array) of points in $\mathbb{R}^3$ s.t. $P = \{p_0,p_1,p_2,...,p_n\}, p_i \in\mathbb{R}^3$. I want to sort $P$ so that every 4 consecutive points forms a non-coplanar ...
yosmo78's user avatar
  • 187
3 votes
0 answers

Periodic 4D Triangulations

I am looking for references and/or algorithms for generating 4-dimensional periodic triangulations on unit 4 lattices. That is, generating a space filling triangulation of the 4D integer lattice (Z^4) ...
user143907's user avatar
1 vote
0 answers

How does Bowyer-Watson algorithm for Delaunay triangulation run in $O(n^2)$ but runs over all the simplexes?

The Bowyer-Watson algorithm for Delaunay triangulation is known to run in $O(n^2)$ according to the authors, where $n$ is the number of data points in $\mathbb R^d$. In addition, the algorithm (for ...
Joe Doe's user avatar
  • 11
-1 votes
2 answers

Solving linear programming problem with mixed type of constraints

I have a query in solving the problem below: An automobile company has two factories. One factory has 400 cars (of a certain model) in stock and the other factory has 300 cars (of the model) in stock. ...
Jayajit's user avatar
5 votes
1 answer

What algorithm do SVMs use to minimize their objective function?

Support Vector Machines turn machine learning linear classification tasks into a linear optimization problems. $$ \text{minimize } J(\theta,\theta_0) = \frac1n \sum_1^n \text{HingeLoss}(\theta,\...
HelloWorld's user avatar
2 votes
1 answer

Better way to decide if a set is a pure simplicial complex

Setup I am trying to write a function that determines if a set of vertices, edges and faces is a pure simplicial complex. A pure simplicial complex is a set where all facets have the same degree, a ...
Makogan's user avatar
  • 341
0 votes
1 answer

In a LP problem Ax = b, how to solve for A instead of x?

I have a multi-objective linear programming problem of the form Ax = b, where A is a matrix and x and b are vectors. x is known, and I'm looking to minimise each row of b by solving for A. Constraints ...
Dom J's user avatar
  • 103
3 votes
1 answer

How to uniformly sample a sorted simplex

I am looking for an algorithm to uniformly generate a descending array of N random numbers, such that the sum of the N numbers is 1, and all numbers lie within 0 and 1. For example, N=3, the random ...
cloudygoose's user avatar