Skip to main content

Questions tagged [topology]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
32 views

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

Say I have N points sampled on a surface in 3 dimensions (ie. points on the surface of a sphere, 1-torus etc.). Is there an algorithm that would be able to count the number of holes in the surface ...
Nikolaj's user avatar
  • 11
1 vote
0 answers
28 views

ensure connectivity in geometric optimization

I am working on parts of my master-thesis and got to a problem which I would like to solve and develop some algorithm for. Basically I am dealing with 2d-geometry which I would like to represent using ...
Finn Eggers's user avatar
4 votes
4 answers
182 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 ...
Mike Metcalf's user avatar
3 votes
2 answers
150 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 ...
Dannyu NDos's user avatar
1 vote
1 answer
215 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 ...
Makogan's user avatar
  • 341
0 votes
0 answers
43 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(...
John He's user avatar
2 votes
2 answers
168 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 ...
Makogan's user avatar
  • 341
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 ...
cs questions's user avatar
1 vote
1 answer
80 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: ...
Dannyu NDos's user avatar
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 ...
Simon Shi's user avatar
1 vote
0 answers
36 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 ...
mathematrucker's user avatar
1 vote
1 answer
589 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, ...
Sam Winnick's user avatar
2 votes
2 answers
97 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 ...
Dannyu NDos's user avatar
0 votes
0 answers
25 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 ...
A T K's user avatar
  • 1
2 votes
0 answers
60 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. ...
Ms. Molly Stewart-Gallus's user avatar
6 votes
1 answer
103 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 ...
Justin Solomon's user avatar
0 votes
0 answers
24 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 $...
Good to learn everything's user avatar
0 votes
0 answers
26 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 ...
plsHelpMe's 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?
Dan's user avatar
  • 11
3 votes
2 answers
719 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 ...
Dannyu NDos's user avatar
2 votes
0 answers
148 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 ...
osobennyj's user avatar
10 votes
1 answer
167 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 ...
helianthus's user avatar
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 ...
bilanush's user avatar
  • 263
1 vote
1 answer
276 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 ...
cvcs5's user avatar
  • 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 ...
juhist's user avatar
  • 283
7 votes
0 answers
473 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 ...
ryan's user avatar
  • 4,511
5 votes
2 answers
124 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 ...
user56834's user avatar
  • 3,922
3 votes
1 answer
2k 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 ...
Lance's user avatar
  • 2,243
2 votes
0 answers
33 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, ...
Eben Kadile's user avatar
-1 votes
1 answer
128 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 ...
someone12321's user avatar
  • 1,428
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, ...
user63364's user avatar
3 votes
0 answers
122 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 ...
Marouane's user avatar
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 ...
S.E.K.'s user avatar
  • 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, ...
John Forkosh's user avatar
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 $...
Kaveh's user avatar
  • 22.3k
1 vote
1 answer
184 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 ...
Mert Metin's user avatar
3 votes
2 answers
3k 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 ...
user3406792's user avatar
15 votes
1 answer
839 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 ...
Pranav's user avatar
  • 359
5 votes
0 answers
129 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 ...
Mark Dominus's user avatar
  • 1,537