Questions tagged [topology]
The topology tag has no usage guidance.
38
questions
4
votes
4
answers
161
views
Minimum Number of Unique Identifiers for a Grid of Cells
I have a grid of cells, X cells wide by Y cells high. Each cell has four corners, NW, NE, SW and SE. Each corner is shared with adjacent neighbors; i.e., a cell's SW corner is the NW corner of the ...
- 163
3
votes
2
answers
137
views
Does this esoteric representation of integers have decidable equality?
Consider the following datatypes in Haskell:
data Foo = Halt | Iter Foo
newtype BigInt = BigInt {nthBit :: Foo -> Bool}
Foo ...
- 313
1
vote
1
answer
186
views
How to turn a 3D polytope into a mesh?
Let us say you have a polyotpe define as the intersection of halfplanes. That is you are given N half-spaces. The polytope is the volume defined by all points which lie on the positive side of all N ...
- 291
0
votes
0
answers
22
views
Convert NURBS surface into Cubic Bezier Surface
The following post discussed how to convert(approximate) NURBS curve into cubic Bézier curve:
Convert NURBS curve into Cubic Bezier Curve
I am trying to come up with an algorithm that converts(...
- 1
0
votes
0
answers
41
views
Can a computer demonstrate that a topological space is compact?
Since all admissible spaces are second-countable and $T_0$, along with Urysohn's metrization theorem, this gives the hierarchy of topological properties of admissible spaces as Hausdorff ⇐ metrizable ⇐...
- 313
2
votes
2
answers
84
views
How to handle coplanarity in convex hull?
I implemented the $O(n^2)$ convex hull algorithm. That is:
Find a triangle known to be in the hull (by finding the lowest point, a point connected to it in the 2D convex hull, and the point that ...
- 291
0
votes
0
answers
75
views
Recovering graph given degrees and connectivity information
I have a graph and don't know how nodes in it are connected to each other.
I know the number of nodes in the graph.
I know the degree of each node in the graph.
I know that given any node $A$ that ...
- 21
1
vote
1
answer
72
views
If a computer can demonstrate singleton sets are closed, is the space Hausdorff?
In Haskell, I made a class of admissible (that is, second-countable and $T_0$) spaces:
...
- 313
3
votes
0
answers
38
views
How to get the minimal enclosed polyhedra in a Line framework (points connectivity lists)?
Greetings all and thank you. I'm a Ph.D. candidate working on a force structure's 3D tessellation project and get stuck.
I've simplified the system into a set of lines linked together which formed a ...
- 31
1
vote
0
answers
32
views
How to compute all inequivalent (under Aut(P)) nonnegative integer weight assignments (with fixed sum) to the vertices of a finite poset P?
Let $P$ be a poset on $n$ points, $\text{Aut}(P)$ its automorphism group, and $a_1,a_2,\dots,a_k$ the lengths of the orbits under $\text{Aut}(P)$.
Goal: An algorithm to generate a member from each ...
- 123
1
vote
1
answer
397
views
What's an example of a planar graph with two embeddings whose geometric duals are nonisomorphic?
How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?
In the post linked above, the user "plop" gives a great response where they claim, in particular, ...
- 11
2
votes
2
answers
95
views
Is it valid to make an admission of a topological space by a "partial quotient map"?
It is well-known that the Sierpiński space, $\{F,T\}$ endowed with topology $\{\emptyset, \{F\},\{F,T\}\}$, is admissible. I tried to implement it in Haskell.
First I implement $\mathbb{N}$ (including ...
- 313
0
votes
0
answers
23
views
Classification of the Summit supercomputer
Can we classify a supercomputer in more than one group? For example, Flynn's classification, classification according to topology, classification according to memory access.
For the Summit ...
- 1
2
votes
0
answers
56
views
What does point-free mean mathematically?
Point-free style is generally taken to mean a style of programming without explicit variables.
I have some intuitions on point-free style but I want to know what the formal mathematical definition is.
...
6
votes
1
answer
100
views
Closest point in embedded simplicial complex
Suppose I have a simplicial $k$-complex $\mathcal S$ whose vertices are embedded in Euclidean space $\mathbb R^n$, for roughly $k< n\leq 6$. Examples include triangle mesh surfaces ($k=2$) embedded ...
- 161
0
votes
0
answers
23
views
How to cluster a dataset in which each data point is composed of a set of 2-dimensional coordinates
I have a dataset with totally $1000$ scenarios, each of which is composed of $5$ users' coordinates $(x_i,y_i), \forall i \in \{1,\dots,5\}$. Now, based on users' coordinates, I want to cluster these $...
0
votes
0
answers
24
views
Machine Learning to draw a topology of elements
I'm exploring the idea of using machine learning to draw a topology of elements. For example, imagine a tree representing geological hierarchy (country -> province -> city). All countries are at ...
1
vote
0
answers
30
views
Finding homotopies in a 2-complex
Are there any efficient algorithms to find the shortest homotopy between two paths in a $2$-complex?
- 11
3
votes
2
answers
683
views
What is the "continuity" as a term in computable analysis?
Background
I once implemented a datatype representing arbitrary real numbers in Haskell. It labels every real numbers by having a Cauchy sequence converging to it. That will let $\mathbb{R}$ be in the ...
- 313
2
votes
0
answers
143
views
Topology mapping (NoC)
My challenge is to derive three mapping scenarios separately for each memory module of the MPEG-4 to the 2-D mesh, so each task is mapped to a different core, and tasks are executed in parallel.
Here ...
- 21
10
votes
1
answer
152
views
Analogue of the topology-computability correspondence for computational complexity
There is an interesting correspondence between notions of topology and notions of computability theory originating from the ingenious idea of Dana Scott to identify computable functions with ...
- 101
2
votes
2
answers
1k
views
Does DFS in an unweighted DAG find the shortest path for each vertex from a source?
I have many questions which related to this topic.
I saw somewhere that a topological sorting can be used to find shortest path, and in DAG it can even find shortest weighted paths of all vertex by ...
- 263
1
vote
1
answer
195
views
How to solve the minimum-cost flow problem on a complete graph, with a concave cost function of flow for each edge?
Here is the problem:
Input:
A series of source/sink nodes at fixed positions with given outwards/inwards flow
Edges are NOT specified. The edges can connect any nodes.
The total source and sink ...
- 13
0
votes
3
answers
3k
views
How to do a reverse topological sort using depth first search?
I'm doing a replacement for the venerable make utility that will support, among other things, automatic cleaning. The utility figures out automatically what files ...
- 283
5
votes
0
answers
419
views
Minimum Number of Edges Added to a DAG to get Unique Topological Order
The question is simple:
Given an unweighted directed acyclic graph, $G = (V, E)$, what is the minimum number of directed edges we need to add to $E$ such that the resulting graph $G = (V, E')$ has ...
- 4,421
5
votes
2
answers
107
views
Topology vs sigma-algebra's as a framework for approximate information?
In the book "topology via logic" by Steven Vickers, topology is introduced for computer scientists, with the idea that topology captures the idea of approximate information.
I am somewhat confused ...
- 3,622
3
votes
1
answer
1k
views
Convert NURBS curve into Cubic Bezier Curve
From this:
Maybe you already know this, but it's impossible to convert nurbs to bezier splines exactly because nurbs are rational functions, and bezier splines are polynomials.
I don't understand ...
- 2,163
2
votes
0
answers
31
views
In topological data analysis, do bar codes that begin and end at the same index mean anything?
The typical workflow in topological data analysis is from point cloud data to filtration to a list of bar codes corresponding to each dimension.
A filtration is a sequence of simplicial complexes, ...
- 235
-1
votes
1
answer
120
views
Sort sequence from topological sort if another value is being important
We have sequence that we got from topological sort, but because the graph may not be connected in all cases, we should sort this sequence with another factor.
We should output permutation of numbers ...
- 1,408
8
votes
0
answers
114
views
Data Structures for Non-Orientable Manifolds
I am looking for a data structure to represent non-orientable manifolds (i.e. meshes like Moebius Strip, but without self-intersection). I will then implement other algorithms using this DS such as, ...
- 81
3
votes
0
answers
115
views
Find internal surfaces in an oriented mesh
I have a solid with internal holes. My solid is mostly a union between walls/floors/ceilings. Each of them is a mesh with polygons oriented counter-clockwise. Then with those polygons I do a union ...
- 31
3
votes
1
answer
1k
views
Meaning of topological distance between 2 pixels
I came across the notion of topology and topological distance in the context of image processing several times (especially when it came to mathematical morphology). I looked for a not too abstract ...
- 33
3
votes
0
answers
146
views
Scott/Lawson topology for function space domain
Given two domains, $D_1$, $D_2$,
already equipped with Scott (or Lawson) topology,
the product domain $D=D_1\times D_2$
has the Tychonoff product topology, e.g.,
Mathematical Theory of Domains, ...
- 305
8
votes
1
answer
1k
views
Is there a continuous hash?
Questions:
Can there be a (cryptographically secure) hash that preserves the information topology of $\{0,1\}^{*}$?
Can we add an efficiently computable closeness predicate which given $h_k(x)$ and $...
- 22.1k
1
vote
1
answer
180
views
Determining on whether topology is a tree or a hypercube
Assume that the nodes know that the topology G is either a hypercube or a
tree. Assuming a unique initiator, design an algorithm to discover the topology. In other words, you would like a node to ...
- 121
3
votes
2
answers
2k
views
Divide self-intersecting polygon into simple polygons
My question is similar to question here Divide self-intersecting polygon
I have points of self-intersecting polygon, its edges and also I am able to find points where it intersects.
I have to divide ...
- 31
15
votes
1
answer
835
views
Testing whether a tetrahedron lies inside a Polyhedron
I have a tetrahedron $t$ and a polyhedron $p$. $t$ is constrained such that it always shares all its vertices with $p$. I want to determine whether $t$ lies inside $p$.
I would like to add one detail ...
- 359
5
votes
0
answers
125
views
Elementary proof of compact space = exhaustible space?
The work of Martín Escardó has demonstrated close parallels between classical topology o one hand and computability on the other hand. (See for example "Infinite sets that admit fast exhaustive ...
- 1,525