Is there any algorithm to find overlapping edges in a graph?

Question

I'm solving extended version of knight tour problem, in which program has to return maximum number of cells through which knight can come back to initial position without overlapping its path. I'm using backtracking approach but got stuck in detecting overlapping.

you can always consider the real plane and apply a sweep line algorithm to check crossing lines — grodzi, Feb 22 '20 at 18:24
Does the graph really look like that? It doesn't seem to represent knight moves... — trincot, Feb 22 '20 at 18:52
Please further define "overlapping". Can it be as simple as landing twice on the same board square? — Paddy3118, Feb 22 '20 at 23:46
No, here overlapping doesn't mean landing on same square, it is described as path overlap while drawing on 2D plane — NeerajSahani, Feb 23 '20 at 08:22

ruakh · Answer 1 · 2020-02-22T19:10:46.583

3

A graph is defined as a set of vertices plus a set of edges, where an edge is a pair of distinct vertices.

In particular, there is no notion of two edges "intersecting" in the way that you mean, because that's a consequence of how you've chosen to draw the graph — where you've drawn the vertices on the plane — rather than a property of the graph itself. (There is a concept of a "planar graph", meaning a graph that can be embedded in the plane with no edges intersecting; but your graph is a planar graph in that sense, so it's not really what you want.)

So to determine if two line segments intersect, we're outside the area of graph theory. Fortunately, there are some pretty straightforward ways to do this; I see that How can I check if two segments intersect? lists several. The approach that came first to my mind (and is used by a few of the highest-voted answers there) is to observe that line segments AB and CD intersect if and only if ∠CAB and ∠BAD have the same sense (clockwise vs. counterclockwise; this means that C and D are on opposite sites of AB) and ∠ACD and ∠DCB have the same sense (this means that A and B are on opposite sides of CD). You can determine this by taking the cross-products of the various segments CA, AB, etc., and comparing signs (positive vs. negative). If your coordinates are all integers, then this just requires a bit of integer arithmetic.

edited Feb 22 '20 at 19:10

answered Feb 22 '20 at 18:34

ruakh

175,680
26
273
307

1

OR, they intersect iff A and B are on different sides of CD and C and D are on different sides of AB, which is a little simpler and requires only dot products. – Matt Timmermans Feb 22 '20 at 18:49
@MattTimmermans: I'm sure I'm being obtuse, but -- how would you use dot products to determine whether *A* and *B* are on opposite sides of *CD*? I don't see it. (My angles-and-cross-products thing is intended to determine whether *A* and *B* are on opposite sides of *CD* and *C* and *D* are on opposite sides of *CD*. I'm definitely open to a simpler way to do that.) – ruakh Feb 22 '20 at 19:00
@MattTimmermans: Oh, I see -- if you construct the normal, as described at https://stackoverflow.com/a/3840235/978917 and https://stackoverflow.com/a/17198094/978917, you can take dot-products of angles relative to that normal. Personally I don't consider that simpler -- and I notice that that question has several higher-voted answers that implicitly or explicitly use cross products, so I'm not alone -- but "simpler" is subjective, and reasonable people can disagree. I'll edit the answer to link to that question, so the OP can choose the approach (s)he likes best. :-) – ruakh Feb 22 '20 at 19:06
It's easier in Cartesian coords. A and B are on different sides of CD if (Ax-Cx,Ay-Cy)\dot(Dy-Cy,Cx-Dx) and (Bx-Cx,By-Cy)\dot(Dy-Cy,Cx-Dx) have different signs. – Matt Timmermans Feb 22 '20 at 19:17
@MattTimmermans: Oh, I see. But once you expand out the cross-product and dot-product calculations into something you can do with integers and floats, they both come out the same: both are just checking whether `(Ax-Cx) * (Dy-Cy) + (Ay-Cy) * (Cx-Dx)` has the same sign as `(Bx-Cx) * (Dy-Cy) + (By-Cy) * (Cx-Dx)`. It's just a matter of whether you choose to interpret those expressions as the normal components of cross products vs. as dot products with normal vectors. (Which is really cool -- I'd never noticed that relationship before! -- but IMHO makes it hard to argue that one is "simpler".) – ruakh Feb 22 '20 at 21:14

score 0 · Answer 2 · answered Feb 22 '20 at 19:15

If this problem is restricted to knight moves, then we can consider that the number of ways that knight moves can intersect is limited (at most 9, not considering direction). For instance, if we have (on a standard chessboard) the move d3-e5, then the only knight moves that intersect are: e2-e4, c3-e4, e3-c4, e3-d5, f3-d4, d4-f5, e4-c5, e4-d6, and f4-d5 -- again, without considering direction. Near the edge of the board there would of course be fewer of those.

This means that you can spend constant time per move to mark those potentially crossing edges as no longer available, and continue the search only along available edges. To allow backtracking, you save on the (recursion) stack which edges you made unavailable at which move.

Is there any algorithm to find overlapping edges in a graph?

2 Answers2