Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with reference-request
Search options questions only
not deleted
user 337
Reference-request is used when the author needs to know about work related to the question.
7
votes
1
answer
227
views
Voronoi diagram on surface of polyhedron
Does anyone know of work on computing the Voronoi diagram of a set of points on a polyhedron, where distance is measured by shortest paths on the surface?
I am particularly interested in convex polyhe …
- 3,773
21
votes
2
answers
2k
views
Computing the Cheeger constant: feasible for which classes?
Computing the Cheeger constant of a graph, also known as the isoperimetric constant
(because it is essentially a minimum area/volume ratio), is known to be NP-complete.
Generally it is approximated. …
- 3,773
10
votes
1
answer
772
views
Voronoi diagram in a graph
Let $G$ be a graph with (positively) weighted edges.
I want to define the Voronoi diagram for a set of nodes/sites $S$, to
associate with a
node $v \in S$
the subgraph $R(v)$ of $G$ induced by all the …
- 3,773
25
votes
2
answers
2k
views
Is it decidable to determine if a given shape can tile the plane?
I know that it is undecidable to determine if a set of tiles can tile the plane,
a result of Berger using Wang tiles.
My question is whether it is also known to be undecidable to determine
if a single …
- 3,773
44
votes
7
answers
6k
views
Truly random number generator: Turing computable?
I am seeking a definitive answer to whether or not generation of "truly random" numbers
is Turing computable. I don't know how to phrase this precisely.
This StackExchange question on "efficient algo …
- 3,773
10
votes
1
answer
565
views
Finding spanning spiders
Is there a polynomial-time algorithm to find—if one exists—a spanning spider
of a given graph $G$? A spider is a tree with at most one node with degree greater than 2:
I know that various …
- 3,773
16
votes
3
answers
1k
views
Is the 3-sphere recognition problem NP-complete?
It is known that determining whether or not a given triangulated 3-manifold is a 3-sphere
is in NP, via work by
Saul Schleimer in 2004: "Sphere recognition lies in NP"
arXiv:math/0407047v1 [math.GT].
…
- 3,773