Questions tagged [topology]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6
votes
1answer
65 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 ...
0
votes
0answers
14 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
0answers
15 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
0answers
28 views

Finding homotopies in a 2-complex

Are there any efficient algorithms to find the shortest homotopy between two paths in a $2$-complex?
3
votes
2answers
514 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 ...
2
votes
0answers
73 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 ...
9
votes
1answer
113 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 ...
1
vote
2answers
315 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 ...
1
vote
1answer
94 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 ...
0
votes
2answers
304 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 ...
5
votes
0answers
193 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 ...
5
votes
2answers
87 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 ...
2
votes
1answer
462 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
votes
0answers
20 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, ...
-1
votes
1answer
95 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 ...
8
votes
0answers
97 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, ...
3
votes
0answers
99 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 ...
3
votes
2answers
770 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 ...
3
votes
0answers
125 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, ...
8
votes
1answer
750 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 $...
1
vote
1answer
158 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 ...
3
votes
2answers
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 ...
15
votes
1answer
788 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 ...
5
votes
0answers
88 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 ...