8 votes

What is the "continuity" as a term in computable analysis?

Arno's answer provides some very useful background reading material, I would just like to address your specific question about $\mathbb{R}$. Let us first recall a result by Peter Hertling, see Theorem ...
Andrej Bauer's user avatar
  • 30.4k
8 votes
Accepted

What is the "continuity" as a term in computable analysis?

Different people have different views on what the definition of continuity should be, but the way I see it, we should define continuity to be computability relative to some oracle. For example: ...
Arno's user avatar
  • 3,085
4 votes
Accepted

Convert NURBS curve into Cubic Bezier Curve

I assume that your cubic spline is non-rational, meaning $w$ = 1, then this is in general true that exact conversion is not possible. NURBS are rational, so you can model conics, say circle whereas ...
Evil's user avatar
  • 9,455
4 votes
Accepted

Meaning of topological distance between 2 pixels

Nonlinear Signal and Image Processing: Theory, Methods, and Applications defines topological distance as follows. First, you have to define when two pixels are neighbors. The book offers two ...
Yuval Filmus's user avatar
4 votes

Topology vs sigma-algebra's as a framework for approximate information?

What sort of structure we get depends on what we are trying to model. Your starting assumptions may well lead to $\sigma$-algebras, but in computer science we have a certain understanding of "...
Andrej Bauer's user avatar
  • 30.4k
4 votes

Minimum Number of Unique Identifiers for a Grid of Cells

This is one of the 800 possible optimal (2-colour) solutions (including reflections and rotations) to the 4x4 problem, found using an exhaustive search: The optimality is because 16 cells require 16 ...
j_random_hacker's user avatar
3 votes
Accepted

Minimum Number of Unique Identifiers for a Grid of Cells

You can solve the problem using at most $\left\lceil \sqrt{2X} \right\rceil + \left\lceil \sqrt{2Y} \right\rceil + 3$ identifiers as follows: PART 1: Let $G$ be a complete graph over $\left\lceil \...
Inuyasha Yagami's user avatar
3 votes
Accepted

If a computer can demonstrate singleton sets are closed, is the space Hausdorff?

Indeed, having your map frechet available and having your map hausdorff available is equivalent. You can find this in my article Topological aspects of the theory of represented spaces (arXiv). The ...
Arno's user avatar
  • 3,085
2 votes

Topology vs sigma-algebra's as a framework for approximate information?

I don't consider myself knowledgable enough about logic to provide a complete answer myself, but I think the following two posts (1 from math.stackexchange, one from mathoverflow) contain some ...
Dean Gurvitz's user avatar
2 votes

Testing whether a tetrahedron lies inside a Polyhedron

I recently found one solution to this problem in a paper 'Robust inside-outside segmentation using generalized winding numbers' by Alec Jacobson et.al., here. It solves the problem of locating if a ...
Pranav's user avatar
  • 359
2 votes

Analogue of the topology-computability correspondence for computational complexity

The answer to your literal question is neither. The reasoning in your question makes perfect sense, and there are several researchers working on the details on what exactly is analogous to complexity ...
Arno's user avatar
  • 3,085
2 votes

Minimum Number of Unique Identifiers for a Grid of Cells

For a pragmatic solution, I suggest using a SAT solver. Suppose we want to find a valid coloring, using $C$ colors. Let $L=\lceil \lg C \rceil$, so that each color can be encoded as a $L$-bit integer....
D.W.'s user avatar
  • 159k
2 votes
Accepted

Does this esoteric representation of integers have decidable equality?

Fun question! Yes equality is externally decidable here, though I don't know if the procedure is internally expressible in Haskell. Here's a more direct solution: Let ...
Caleb Stanford's user avatar
2 votes

Does this esoteric representation of integers have decidable equality?

Assuming that you intend to only count the total functions for $\mathsf{BigInt}$, then yes, equality should be decidable. Here's a sketch for how to do it for $i$ and $j$: First test $i$ and $j$ on $...
Dan Doel's user avatar
  • 2,687
2 votes

What's an example of a planar graph with two embeddings whose geometric duals are nonisomorphic?

There is an answer in Graph Theory by Bondy and Murty: It is clear that both graphs are isomorphic. Their respective duals are not, because each face of the first dual has degree 3 (except the ...
Nathaniel's user avatar
  • 15.6k
2 votes

Minimum Number of Unique Identifiers for a Grid of Cells

Each Even column of corners (blue arrows) encodes a single unique ‘X’ indicator: x0,x2,x4… (here colored using Red, Green, Blue) Each Odd column of corners (yellow arrows) encode a semi-incrementing ‘...
Mike Metcalf's user avatar
2 votes
Accepted

How to handle coplanarity in convex hull?

If You find a co-planar triangle candidate, it has to be one that does not contain any other points in that plane. I am not familiar with rust so here is a pseudo-code attempt to enhance your code: <...
DirkT's user avatar
  • 991
1 vote

How to topologically classify points in 3d space generating a surface?

You are looking for persistent homology, a branch of computational topology that studies precisely the question you asked. Roughly, the idea is as follows. Pick a "resolution radius $r$", ...
Andrej Bauer's user avatar
  • 30.4k
1 vote
Accepted

Is it valid to make an admission of a topological space by a "partial quotient map"?

When we implement a space we do not actually implement the space itself, but rather a representation of it. That is, an implementation of $X$ consists of a datatype $T$ and a partial surjection $\...
Andrej Bauer's user avatar
  • 30.4k
1 vote

Closest point in embedded simplicial complex

If you have only a single k-complex and you want to get the closest point regardless of whether it is a neighbor, then you can simply use any spatial index that supports nearest neighbor queries. For ...
TilmannZ's user avatar
  • 764
1 vote

Does DFS in an unweighted DAG find the shortest path for each vertex from a source?

Why don't we just use DFS to find shortest path in DAG? For this try to find shortest path from source vertex $0$ to all vertex in following graph. In particular if DFS visits $1$ first from $0$ ...
Vimal Patel's user avatar
1 vote

Does DFS in an unweighted DAG find the shortest path for each vertex from a source?

The only question is in the tile so I'm going to answer that. A DFS visit from a source $s$ of a unweighted DAG $G$ does not find the shortest paths of $G$ from $s$. As a counter example look at the ...
Steven's user avatar
  • 29.5k
1 vote

How to do a reverse topological sort using depth first search?

In order to get the files in the desired order, simply follow the following rule: A node can be deleted iff all of its children have been deleted. This is the same as a postorder traversal of a tree. ...
Throckmorton's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible