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

Abstract

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.

Ένα σύνολο σημείων με k ρίζες P είναι ένα σύνολο σημείων όπου k σημεία του r_1 , r_2 , . . ., r_k ∈ P διαφοροποιούνται από τα υπόλοιπα σημεία του P και αποκαλούνται ρίζες του P. Ένα γεωμετρικό γράφημα με k ρίζες G = (P,E) είναι ένα γεωμετρικό γράφημα όπου το σύνολο των κόμβων του, P, είναι ένα σύνολο σημείων με k ρίζες και οι ρίζες του G είναι οι ρίζες του P. Ένα γεωμετρικό μονοπάτι Q = (q_0, q_1, . . ., q_t) είναι y−μονότονο αν η ακολουθία των y−συντεταγμένων των σημείων του Q, δηλαδή η ακολουθία y(q_0), y(q_1), . . ., y(q_t), είναι μονότονη. Ένα γεωμετρικό γράφημα με k ρίζες G = (P,E) είναι y−μονότονο με k ρίζες αν κάθε ρίζα r ∈ P και κάθε σημείο p ∈ P \ {r} συνδέονται με κάποιο y−μονότονο μονοπάτι. Δοθέντος ενός συνόλου σημείων με k ρίζες P το y−μονότονο ελάχιστο συνδετικό γράφημα με k ρίζες του P είναι το y−μονότονο συνδετικό γράφημα με k ρίζες του P με το ελάχιστο κόστος. Το κόστος ενός γεωμετρικού γραφήματος είναι το άθροισμα των μηκών των ακμών του. Ασχολούμαστε με το πρόβλημα της εύρεσης του y−μονότονου ελάχιστου συνδετικού γραφήματος με ρίζα ενός συνόλου σημείων με ρίζα P. Χτίζοντας πάνω σε προηγούμενα αποτελέσματα δείχνουμε ότι το y−μονότονο ελάχιστο συνδετικό γραφήμα με ρίζα του P (i) είναι ένα δέντρο το οποίο αποκαλούμε το y−μονότονο ελάχιστο συνδετικό δέντρο με ρίζα του P και (ii) εξάγεται σε O(|P|log^2 |P|) χρόνο. Μελετάμε επίσης το πρόβλημα της απεικόνισης ενός δέντρου με ρίζα ως ένα y−μονότονο ελάχιστο συνδετικό δέντρο με ρίζα. Αρχικά δίνουμε ένα γραμμικού χρόνου αλγόριθμο ο οποίος απεικονίζει ένα δέντρο με ρίζα ως ένα y−μονότονο ελάχιστο συνδετικό δέντρο με ρίζα. Πόρισμα της προηγούμενης πρότασης είναι ότι δεν υπάρχει σταθερά C τέτοια ώστε ο μέγιστος βαθμός κάθε y−μονότονου ελάχιστου συνδετικού δέντρου με ρίζα να είναι φραγμένος από τη C. Επιπλέον δείχνουμε ότι υπάρχουν δέντρα με ρίζα για τα οποία κάθε απεικονιση στο πλέγμα ως ένα y−μονότονο ελάχιστο συνδετικό δέντρο με ρίζα απαιτεί ένα πλέγμα με εκθετικό εμβαδό. Δίνουμε ακόμα έναν απλό 2−προσεγγιστικό αλγόριθμο για το πρόβλημα της εύρεσης του y−μονότονου ελάχιστου συνδετικού γραφήματος με k ρίζες ενός συνόλου σημείων με k ρίζες P. Ένα γεωμετρικό γράφημα με ρίζα G είναι ομοιόμορφα μονότονο με ρίζα αν είναι y′−μονότονο με ρίζα για κάποιον άξονα y′. Παρέχουμε έναν O(|E|log|P|) χρόνου αλγόριθμο που καθορίζει αν ένα γεωμετρικό γράφημα με ρίζα G = (P,E) είναι ομοιόμορφα μονότονο με ρίζα. Επιπρόσθετα ασχολούμαστε με το πρόβλημα της εύρεσης του ομοιόμορφα μονότονου ελάχιστου συνδετικού δέντρου με ρίζα ενός συνόλου σημείων με ρίζα P, όπου το ομοιόμορφα μονότονο ελάχιστο συνδετικό δέντρο με ρίζα του P είναι το ομοιόμορφα μονότονο συνδετικό δέντρο με ρίζα του P με το ελάχιστο κόστος. Δείχνουμε ότι το ομοιόμορφα μονότονο ελάχιστο συνδετικό δέντρο με ρίζα του P εξάγεται σε O(|P|^2 log|P|) χρόνο. Ένα γεωμετρικό μονοπάτι Q = (q_0, q_1, . . . , q_t) είναι xy−μονότονο αν και η ακολουθία των x−συντεταγμένων των σημείων του Q, δηλαδή η ακολουθία x(q_0), x(q_1), . . ., x(q_t), είναι μονότονη και η ακολουθία των y−συντεταγμένων των σημείων του Q, δηλαδή η ακολουθία y(q_0), y(q_1), . . ., y(q_t), είναι μονότονη. Το γεωμετρικό μονοπάτι Q είναι 2K−μονότονο αν είναι x′y′−μονότονο για κάποιο Καρτεσιανό Σύστημα Συντεταγμένων x′y′. Ένα γεωμετρικό γράφημα G = (P,E) είναι 2K−μονότονο αν κάθε ζευγάρι σημείων του P συνδέεται με ένα 2K−μονότονο μονοπάτι. Μελετάμε το πρόβλημα της παραγωγής 2K−μονότονων συνδετικών γραφημάτων σε σύνολα σημείων σε κυρτή θέση. Εξάγουμε ότι δοθέντος ενός συνόλου σημείων σε κυρτή θέση P παράγεται ένα 2K−μονότονο συνδετικό γράφημα που έχει ως σύνολο κόμβων το P μαζί με λιγότερο από ή ίσο με ένα Steiner σημείο (δηλαδή ένα επιπρόσθετο σημείο που δεν δίνεται ως είσοδος) και έχει λιγότερες από ή ίσες με 4|P| − 8 ακμές. Ένα γεωμετρικό γράφημα G = (P,E) λέγεται xy−μονότονο αν κάθε ζευγάρι κόμβων του G συνδέεται με ένα xy−μονότονο μονοπάτι. Δοθέντος ενός συνόλου σημείων P το xy−μονότονο ελάχιστο συνδετικό γράφημα του P είναι το xy−μονότονο συνδετικό γράφημα του P ελάχιστου κόστους. Μελετάμε το πρόβλημα της εύρεσης του xy−μονότονου ελάχιστου συνδετικού γραφήματος ενός συνόλου σημείων P και το πρόβλημα της εύρεσης του xy−μονότονου συνδετικού γραφήματος με το ελάχιστο πλήθος ακμών ενός συνόλου σημείων P. Χτίζοντας πάνω σε προηγούμενα αποτελέσματα εξάγουμε εύκολα ότι δοθέντος ενός συνόλου σημείων P το xy−μονότονο ελάχιστο συνδετικό γράφημα του P είναι ίσο με το xy−μονότονο συνδετικό γράφημα με το ελάχιστο πλήθος ακμών του P και τα δύο αυτά είναι ίσα με το γράφημα του ορθογωνίου επιρροής του P. Όπου το γράφημα του ορθογωνίου επιρροής ενός συνόλου σημείων P είναι το γεωμετρικό γράφημα με σύνολο κόμβων το P όπου οι κόμβοι p και q συνδέονται με ακμή αν και μόνο αν το ορθογώνιο με γωνιακά σημεία τα p και q και πλευρές παράλληλες στους άξονες του Καρτεσιανού Συστήματος Συντεταγμένων δεν περιέχει άλλα σημεία (εκτός από τα p και q) του P. Το γεωμετρικό γράφημα G λέγεται ομοιόμορφα 2K−μονότονο αν υπάρχει Καρτεσιανό Σύστημα Συντεταγμένων x′y′ τέτοιο ώστε το G να είναι x′y′−μονότονο. Το ομοιόμορφα 2K−μονότονο ελάχιστο συνδετικό γράφημα ενός συνόλου σημείων P είναι το ομοιόμορφα 2K−μονότονο συνδετικό γράφημα του P ελάχιστου κόστους. Μελετάμε επίσης το πρόβλημα της εύρεσης του ομοιόμορφα 2K−μονότονου ελάχιστου συνδετικού γραφήματος ενός συνόλου σημείων P και το πρόβλημα της εύρεσης του ομοιόμορφα 2K−μονότονου συνδετικού γραφήματος με το ελάχιστο πλήθος ακμών ενός συνόλου σημείων P. Σημειώνουμε ότι δοθέντος ενός συνόλου σημείων P το ομοιόμορφα 2K−μονότονο ελάχιστο συνδετικό γράφημα του P δεν ταυτίζεται πάντα με το ομοιόμορφα 2K−μονότονο συνδετικό γράφημα με το ελάχιστο πλήθος ακμών του P. Όμως δείχνουμε ότι και το ομοιόμορφα 2K−μονότονο ελάχιστο συνδετικό γράφημα του P και το ομοιόμορφα 2K−μονότονο συνδετικό γράφημα με το ελάχιστο πλήθος ακμών του P μπορούν να παραχθούν σε O(|P|^3) χρόνο. Ένα γεωμετρικό γράφημα G = (P,E) με ρίζα r λέγεται xy−μονότονο με ρίζα αν κάθε κόμβος του G διαφορετικός από τη ρίζα συνδέεται με την r με ένα xy−μονότονο μονοπάτι. Έστω P ένα σύνολο σημείων με ρίζα τότε το xy−μονότονο ελάχιστο συνδετικό γράφημα με ρίζα του P είναι το xy−μονότονο συνδετικό γράφημα με ρίζα του P ελάχιστου κόστους. Δείχνουμε ότι το xy−μονότονο ελάχιστο συνδετικό γραφήμα με ρίζα του P είναι ένα δέντρο το οποίο αποκαλούμε το xy−μονότονο ελάχιστο συνδετικό δέντρο με ρίζα του P και το οποίο εξάγεται σε O(|P|log^3 |P|) χρόνο. Το γεωμετρικό γράφημα με ρίζα G λέγεται ομοιόμορφα 2K−μονότονο με ρίζα αν υπάρχει Καρτεσιανό Σύστημα Συντεταγμένων x′y′ τέτοιο ώστε το G να είναι x′y′−μονότονο με ρίζα. Παρέχουμε έναν αλγόριθμο που καθορίζει αν ένα γεωμετρικό γράφημα με ρίζα G = (P,E) είναι ομοιόμορφα 2K−μονότονο με ρίζα σε O(|E|log|P|) χρόνο. Το ομοιόμορφα 2K−μονότονο ελάχιστο συνδετικό δέντρο με ρίζα ενός συνόλου σημείων με ρίζα P είναι το ομοιόμορφα 2K−μονότονο συνδετικό δέντρο με ρίζα του P ελάχιστου κόστους. Δείχνουμε ότι το ομοιόμορφα 2K−μονότονο ελάχιστο συνδετικό δέντρο με ρίζα του P εξάγεται σε O(|P|^2 log|P|) χρόνο.