Powered by OpenAIRE graph
Found an issue? Give us feedback
addClaim

Monotone path queries and monotone subdivision problems in polygonal domains

Authors: Wei, Xiangzhi;

Monotone path queries and monotone subdivision problems in polygonal domains

Abstract

In this thesis, we explore two problems in geometry, both related to monotonicity. The problem of finding monotone paths between two given points has useful applications in path planning, and in particular it is useful to look for minimum link paths. We are given a simple polygon P or a polygonal domain D with n vertices, and a triplet of query parameters: (s, t, d), where s and t are two points in the plane and d is any direction. We show how to answer a query for the existence of a d-monotone path between s and t inside P (or D) in logarithmic time by preprocessing P (or D) in an efficient way. Our approach is based on a novel idea utilizing the dual graph of the trapezoidal map of P (or D). Furthermore, we also show how to output a minimum link d-monotone path between points s and t, for an arbitrary input triplet (s, t, d). Polygon partitioning is another important problem in computational geometry. We address the problem of partitioning a polygonal domain D into a minimum number of uniformly monotone components, allowing Steiner points. We show that for a given monotone direction, this problem is solvable in O(nlogn + rR) time, where n is the number of vertices of D, r is the number of scan reflex vertices of D, and R is the total number of reflex vertices of D. Further, if E is the size of the visibility graph of the polygon, then the optimal uniformly monotone subdivision can be queried in O(E(n + R1.5log2R)) time, and reported in O(rR) time. We also provide upper bounds on the number of components as well as on the number of Steiner points in such an optimal subdivision.

Country
China (People's Republic of)
Keywords

Polygons, Monotone operators, 511, Geometry -- Data processing

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!