Publicación:
EFFICIENT COMPUTATION OF THE CONVEX HULL ON SETS OF POINTS STORED IN A K-TREE COMPACT DATA STRUCTURE

dc.creatorCARLOS FELIPE QUIJADA FUENTES
dc.creatorMIGUEL ESTEBAN ROMERO VÁSQUEZ
dc.creatorMÓNICA ALEJANDRA CANIUPÁN MARILEO
dc.creatorGILBERTO ANTONIO GUTIÉRREZ RETAMAL
dc.date2020
dc.date.accessioned2025-01-10T15:16:16Z
dc.date.available2025-01-10T15:16:16Z
dc.date.issued2020
dc.description.abstractIN THIS PAPER, WE PRESENT TWO ALGORITHMS TO OBTAIN THE CONVEX HULL OF A SET OF POINTS THAT ARE STORED IN THE COMPACT DATA STRUCTURE CALLED K2-TREE. THIS PROBLEM CONSISTS IN GIVEN A SET OF POINTS P IN THE EUCLIDEAN SPACE OBTAINING THE SMALLEST CONVEX REGION (POLYGON) CONTAINING P. TRADITIONAL ALGORITHMS TO COMPUTE THE CONVEX HULL DO NOT SCALE WELL FOR LARGE DATABASES, SUCH AS SPATIAL DATABASES, SINCE THE DATA DOES NOT RESIDE IN MAIN MEMORY. WE USE THE K2-TREE COMPACT DATA STRUCTURE TO REPRESENT, IN MAIN MEMORY, EFFICIENTLY A BINARY ADJACENCY MATRIX REPRESENTING POINTS OVER A 2D SPACE. THIS STRUCTURE ALLOWS AN EFFICIENT NAVIGATION IN A COMPRESSED FORM. THE EXPERIMENTATIONS PERFORMED OVER SYNTHETICAL AND REAL DATA SHOW THAT OUR PROPOSED ALGORITHMS ARE MORE EFFICIENT. IN FACT THEY PERFORM OVER FOUR ORDER OF MAGNITUDE COMPARED WITH ALGORITHMS WITH TIME COMPLEXITY OF O(NLOGN).
dc.formatapplication/pdf
dc.identifier.doi10.1007/s10115-020-01486-9
dc.identifier.issn0219-3116
dc.identifier.issn0219-1377
dc.identifier.urihttps://repositorio.ubiobio.cl/handle/123456789/11219
dc.languagespa
dc.publisherKNOWLEDGE AND INFORMATION SYSTEMS
dc.relation.uri10.1007/s10115-020-01486-9
dc.rightsPUBLICADA
dc.titleEFFICIENT COMPUTATION OF THE CONVEX HULL ON SETS OF POINTS STORED IN A K-TREE COMPACT DATA STRUCTURE
dc.title.alternativeCÁLCULO EFICIENTE DEL CASCO CONVEXO EN CONJUNTOS DE PUNTOS ALMACENADOS EN UNA ESTRUCTURA DE DATOS COMPACTA DE K-TREE
dc.typeARTÍCULO
dspace.entity.typePublication
ubb.EstadoPUBLICADA
ubb.Otra ReparticionDEPARTAMENTO DE CIENCIAS DE LA COMPUTACION Y TECNOLOGIA DE LA INFORMACION.
ubb.Otra ReparticionDEPARTAMENTO DE CIENCIAS DE LA COMPUTACION Y TECNOLOGIA DE LA INFORMACION.
ubb.Otra ReparticionDEPARTAMENTO DE SISTEMAS DE INFORMACION
ubb.Otra ReparticionDEPARTAMENTO DE CIENCIAS DE LA COMPUTACION Y TECNOLOGIA DE LA INFORMACION.
ubb.SedeCHILLÁN
ubb.SedeCHILLÁN
ubb.SedeCONCEPCIÓN
ubb.SedeCHILLÁN
Archivos