National Technical University of Athens (NTUA)
Γεωμετρικά γραφήματα με y-μονότονα και xy-μονότονα μονοπάτια: κατασκευή και αναγνώριση
Abstract
dc:descriptionA point set P is k−rooted if there exist k points r_1 , r_2 , ..., r_k ∈ P distinguished from the other points of P which are called the roots of P. A geometric graph G = (P,E) is called k−rooted if P is k−rooted and its roots are the roots of P. A geometric path Q = (q_0, q_1, ..., q_t) is called y−monotone if the sequence of the y−coordinates of the points of Q, i.e. the sequence y(q_0), y(q_1), ..., y(q_t), is monotone. A k−rooted geometric graph G = (P,E) is k−rooted y−monotone if each root r ∈ P and each point p ∈ P \ {r} are connected by a y−monotone path. The k−rooted y−monotone minimum spanning graph of a k−rooted point set P is the k−rooted y−monotone spanning graph of P that has the minimum cost. The cost of a geometric graph is the sum of the lengths of its edges. We deal with the problem of obtaining the rooted y−monotone minimum spanning graph of a rooted point set P. Building upon previous results we show that the rooted y−monotone minimum spanning graph of P (i) is a tree which we call the rooted y−monotone minimum spanning tree of P and (ii) it is obtained in O(|P|log^2 |P|) time. We also study the problem of drawing a rooted tree as a rooted y−monotone minimum spanning tree. We initially give a linear-time algorithm that draws a rooted tree as a rooted y−monotone minimum spanning tree. A corollary of the previous sentence is that there is no constant number C such that the maximum degree of every rooted y−monotone minimum spanning tree to be bounded by C. We also show that there exist rooted trees for which any grid drawing as a rooted y−monotone minimum spanning tree requires a grid of exponential area. Additionally, we give a simple 2−approximation algorithm for the problem of producing the k−rooted y−monotone minimum spanning graph of a k−rooted point set P. A rooted geometric graph G = (P,E) is rooted uniform monotone if it is rooted y′−monotone for some axis y′. We provide a O(|E|log|P|) time algorithm that determines if a rooted geometric graph G = (P,E) is rooted uniform monotone. Additionally we deal with the problem of producing the rooted uniform monotone minimum spanning tree of a rooted point set P, where the rooted uniform monotone minimum spanning tree of P is the rooted uniform monotone spanning tree of P that has the minimum cost. We show that the rooted uniform monotone minimum spanning tree of P is obtained in O(|P|^2 log|P|) time. A geometric path Q = (q_0, q_1, ..., q_t) is called xy−monotone if both the sequence of the x−coordinates of the points of Q, that is the sequence x(q_0), x(q_1), . . ., x(q_t), is monotone and the sequence of the y−coordinates of the points of Q, that is the sequence y(q_0), y(q_1), . . ., y(q_t), is monotone. The geometric path Q is 2D-monotone if it is x′y′−monotone for a Cartesian Coordinate System x′y′. A geometric graph G = (P,E) is 2D-monotone if each pair of points of P is connected by a 2D-monotone path. We study the problem of producing 2D-monotone spanning graphs on convex point sets. We obtain that given a convex point set P a 2D-monotone spanning graph that has as node set the point set P along with less than or equal to one Steiner point (that is an additional point which is not given as input) and has less than or equal to 4|P| − 8 edges is produced. A geometric graph G = (P,E) is xy−monotone if each pair of nodes of G is connected by a xy−monotone path. The xy−monotone minimum spanning graph of a point set P is the xy−monotone spanning graph of P that has the minimum cost. We study the problem of producing the xy−monotone minimum spanning graph of a point set P and the problem of producing the xy−monotone spanning graph that has the least number of edges of a point set P. Building upon previous results, we easily obtain that given a point set P the xy−monotone minimum spanning graph of P is equal to the xy−monotone spanning graph that has the least number of edges of P and that both of them are equal to the rectangle of influence graph of P. Where the rectangle of influence graph of a point set P is the geometric graph with P as its node set where the nodes p and q are connected by an edge if and only if the rectangle with corners p and q and edges parallel to the axes of the Cartesian Coordinate System does not include any other points (except for p and q) of P. The geometric graph G is uniform 2D-monotone if there exists a Cartesian Coordinate System x′y′ such that G is x′y′−monotone. The uniform 2D-monotone minimum spanning graph of a point set P is the uniform 2D-monotone spanning graph of P that has the minimum cost. We also study the problem of producing the uniform 2D-monotone minimum spanning graph of a point set P and the problem of producing the uniform 2D-monotone spanning graph with the least number of edges of a point set P. We note that given a point set P the uniform 2D-monotone minimum spanning graph of P does not always coincide with the uniform 2D-monotone spanning graph with the least number of edges of P. But we show that both the uniform 2D-monotone minimum spanning graph of P and the uniform 2D-monotone spanning graph with the least number of edges of P can be obtained in O(|P|^3) time. A geometric graph G = (P,E) with root r is called rooted xy−monotone if each node of G different from the root r is connected with r by a xy−monotone path. Let P be a rooted point set, the rooted xy−monotone minimum spanning graph of P is the rooted xy−monotone spanning graph of P that has the minimum cost. We show that the rooted xy−monotone minimum spanning graph of P is a tree which we call the rooted xy−monotone minimum spanning tree of P and which is obtained in O(|P|log^3 |P|) time. The rooted geometric graph G is rooted uniform 2D-monotone if there exists a Cartesian Coordinate System x′y′ such that G is rooted x′y′−monotone. We provide an algorithm that determines if a rooted geometric graph G = (P,E) is rooted uniform 2D-monotone in O(|E|log|P|) time. The rooted uniform 2D-monotone minimum spanning tree of a rooted point set P is the rooted uniform 2D-monotone spanning tree of P that has the minimum cost. We show that the rooted uniform 2D-monotone minimum spanning tree of a point set P with root r is obtained in O(|P|^2 log|P|) time.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2022
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Mastakas, Konstantinos
- Μάστακας, Κωνσταντίνος
Subjects
dc:subject × 16- y−μονότονα μονοπάτια
- xy−μονότονα μονοπάτια
- Ελάχιστο κόστος
- Ελάχιστο πλήθος ακμών
- Απεικόνιση δέντρων
- y-monotone paths
- xy-monotone paths
- Minimum Cost
- Minimum number of edges
- Tree drawing
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Φυσικές Επιστήμες
- Επιστήμη ηλεκτρονικών υπολογιστών
- Computer and Information Sciences
- Natural Sciences
- Computer Science
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/53220