On d-regular Schematization of Embedded Paths

In the d-regular path schematization problem we are given an embedded path P (e.g.,a route in a road network) and an integer d. The goal is to find a d-schematized embedding
of P in which the orthogonal order of allvertices in the input is preserved and in which every
edge has a slope that is an integer multiple of 90/d. We show that deciding whether a path can
be d-schematized is NP-hard for any integer d. We further model the problem as a mixed-integer linear program. An experimental evaluation indicates that this approach generates reasonable
route sketches for real-world data.