Back to search

National Technical University of Athens (NTUA)

Γεωμετρικά γραφήματα με y-μονότονα και xy-μονότονα μονοπάτια: κατασκευή και αναγνώριση

Abstract

dc:description

A 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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/53220

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Mastakas, Konstantinos; Μάστακας, Κωνσταντίνος. Γεωμετρικά γραφήματα με y-μονότονα και xy-μονότονα μονοπάτια: κατασκευή και αναγνώριση. National Technical University of Athens (NTUA), 2022. http://hdl.handle.net/10442/hedi/53220