• Colored spanning graphs for se...

Result: Colored spanning graphs for set visualization

Title:
Colored spanning graphs for set visualization
Authors:
Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. DCG - Discrete and Combinatorial Geometry, Hurtado Díaz, Fernando Alfredo, Korman, Matias, Van Kreveld, Matias, Löffler, Maarten, Sacristán Adinolfi, Vera, Shioura, Akiyoshi, Silveira, Rodrigo Ignacio, Speckmann, Bettina, Tokuyama, Takeshi
Publisher Information:
2018-03
Document Type:
Electronic Resource Electronic Resource
Index Terms:
Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria computacional, Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi numèrica, Numerical analysis, Algebra, Homological, Approximation, Colored point set, Matroid intersection, Minimum spanning tree, Set visualization, Anàlisi numèrica, Àlgebra homològica, Classificació AMS::65 Numerical analysis::65D Numerical approximation and computational geometry, Classificació AMS::55 Algebraic topology::55U Applied homological algebra and category theory, Article
URL:
https://arxiv.org/abs/1603.00580
http://hdl.handle.net/2117/115386
http://www.sciencedirect.com/science/article/pii/S0925772117300585?via%3Dihub
Availability:
Open access content. Open access content
Open Access
Note:
15 p.
application/pdf
English
Other Numbers:
HGF oai:upcommons.upc.edu:2117/115386
Hurtado, F., Korman, M., Van Kreveld, M., Löffler, M., Sacristán, V., Shioura, A., Silveira, R.I., Speckmann, B., Tokuyama, T. Colored spanning graphs for set visualization. "Computational geometry: theory and applications", Març 2018, vol. 68, p. 262-276.
0925-7721
10.1016/j.comgeo.2017.06.006
1029460954
Contributing Source:
UNIV POLITECNICA DE CATALUNYA
From OAIster®, provided by the OCLC Cooperative.
Accession Number:
edsoai.on1029460954
Database:
OAIster

Further Information

We study an algorithmic problem that is motivated by ink minimization for sparse set visualizations. Our input is a set of points in the plane which are either blue, red, or purple. Blue points belong exclusively to the blue set, red points belong exclusively to the red set, and purple points belong to both sets. A red-blue-purple spanning graph (RBP spanning graph) is a set of edges connecting the points such that the subgraph induced by the red and purple points is connected, and the subgraph induced by the blue and purple points is connected.We study the geometric properties of minimum RBP spanning graphs and the algorithmic problems associated with computing them. Specifically, we show that the general problem can be solved in polynomial time using matroid techniques. In addition, we discuss more efficient algorithms for the case in which points are located on a line or a circle, and also describe a fast (12¿+1)-approximation algorithm, where ¿ is the Steiner ratio.
Peer Reviewed
Postprint (author's final draft)