Questions tagged [topology]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
74 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 ...
user avatar
1 vote
1 answer
61 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: ...
user avatar
3 votes
0 answers
35 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 ...
user avatar
1 vote
0 answers
31 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 ...
user avatar
1 vote
1 answer
145 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, ...
user avatar
2 votes
2 answers
80 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 ...
user avatar
0 votes
0 answers
21 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 ...
user avatar
  • 1
2 votes
0 answers
49 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. ...
user avatar
6 votes
1 answer
93 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 ...
user avatar
0 votes
0 answers
18 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 $...
user avatar
  • 31
0 votes
0 answers
21 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 ...
user avatar
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?
user avatar
  • 11
3 votes
2 answers
599 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 ...
user avatar
2 votes
0 answers
114 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 ...
user avatar
10 votes
1 answer
142 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 ...
user avatar
2 votes
2 answers
884 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 ...
user avatar
  • 263
1 vote
1 answer
147 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 ...
user avatar
  • 13
0 votes
3 answers
1k 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 ...
user avatar
  • 273
5 votes
0 answers
304 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 ...
user avatar
  • 4,361
5 votes
2 answers
98 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 ...
user avatar
  • 3,464
3 votes
1 answer
836 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 ...
user avatar
  • 1,853
2 votes
0 answers
24 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, ...
user avatar
-1 votes
1 answer
106 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 ...
user avatar
  • 1,398
8 votes
0 answers
107 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, ...
user avatar
3 votes
0 answers
105 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 ...
user avatar
3 votes
2 answers
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 ...
user avatar
  • 33
3 votes
0 answers
140 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, ...
user avatar
8 votes
1 answer
974 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 $...
user avatar
  • 21.6k
1 vote
1 answer
177 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 ...
user avatar
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 ...
user avatar
15 votes
1 answer
812 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 ...
user avatar
  • 359
5 votes
0 answers
107 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 ...
user avatar
  • 1,517