La coque convexe est l'une des constructions les plus fondamentales en géométrie et sa construction a été largement étudiée. Il existe de nombreux travaux antérieurs sur la coque convexe des pointes. Cependant, sa contrepartie pour les points pondérés n'a pas été suffisamment prise en compte malgré des applications importantes. Ici, nous présentons un algorithme simple et rapide, QuickhullDisk, pour la coque convexe d'un ensemble de disques dans R2 en généralisant l'algorithme quickhull pour les points. QuickhullDisk prend O(nlog n) temps en moyenne et O(mn) temps dans le pire des cas où m représente le nombre de disques extrêmes qui contribuent à la limite de la coque convexe de n disques. Ces complexités temporelles sont identiques à celles de l'algorithme quickhull pour les points dans R2. Le résultat expérimental montre que l'algorithme QuickhullDisk proposé fonctionne significativement plus rapidement que l'algorithme incrémentiel de temps O(nlog n), proposé par Devillers et Golin en 1995, en particulier pour le big data. QuickhullDisk est environ 2,6 fois plus rapide que l'algorithme incrémentiel pour les disques aléatoires et est 1,2 fois plus rapide même pour les jeux de disques où tous les disques sont extrêmes. Cette accélération est due au fait que l'opération géométrique de base de l'algorithme QuickhullDisk est un prédicat pour la localisation d'un point w.r.t. une ligne et est beaucoup plus rapide que celle de l'algorithme incrémentiel. Le code source de QuickhullDisk est disponible gratuitement auprès de Mendeley Data et une version GUI auprès du Voronoi Diagram Research Center, Université de Hanyang (http://voronoi.hanyang.ac.kr/).

El casco convexo es una de las construcciones más fundamentales en geometría y su construcción ha sido ampliamente estudiada. Hay muchos trabajos previos sobre el casco convexo de los puntos. Sin embargo, su contraparte para los puntos ponderados no se ha abordado lo suficiente a pesar de las importantes aplicaciones. Aquí, presentamos un algoritmo simple y rápido, QuickhullDisk, para el casco convexo de un conjunto de discos en R2 generalizando el algoritmo de casco rápido para puntos. QuickhullDisk tarda O(nlog n) tiempo en promedio y O(mn) tiempo en el peor de los casos, donde m representa el número de discos extremos que contribuyen al límite del casco convexo de n discos. Estas complejidades de tiempo son idénticas a las del algoritmo quickhull para los puntos en R2. El resultado experimental muestra que el algoritmo QuickhullDisk propuesto se ejecuta significativamente más rápido que el algoritmo incremental de tiempo O(nlog n), propuesto por Devillers y Golin en 1995, particularmente para big data. QuickhullDisk es aproximadamente 2,6 veces más rápido que el algoritmo incremental para discos aleatorios y es 1,2 veces más rápido incluso para los conjuntos de discos donde todos los discos son extremos. Esta aceleración se debe a que la operación geométrica básica del algoritmo QuickhullDisk es un predicado para la ubicación de un punto con respecto a una línea y es mucho más rápida que la del algoritmo incremental. El código fuente de QuickhullDisk está disponible gratuitamente en Mendeley Data y una versión de GUI del Centro de Investigación de Diagramas de Voronoi, Universidad de Hanyang (http://voronoi.hanyang.ac.kr/).

Convex hull is one of the most fundamental constructs in geometry and its construction has been extensively studied. There are many prior works on the convex hull of points. However, its counterpart for weighted points has not been sufficiently addressed despite important applications. Here, we present a simple and fast algorithm, QuickhullDisk, for the convex hull of a set of disks in R2 by generalizing the quickhull algorithm for points. QuickhullDisk takes O(nlog n) time on average and O(mn) time in the worst case where m represents the number of extreme disks which contribute to the boundary of the convex hull of n disks. These time complexities are identical to those of the quickhull algorithm for points in R2. Experimental result shows that the proposed QuickhullDisk algorithm runs significantly faster than the O(nlog n) time incremental algorithm, proposed by Devillers and Golin in 1995, particularly for big data. QuickhullDisk is approximately 2.6 times faster than the incremental algorithm for random disks and is 1.2 times faster even for the disk sets where all disks are extreme. This speed-up is because the basic geometric operation of the QuickhullDisk algorithm is a predicate for the location of a point w.r.t. a line and is much faster than that of the incremental algorithm. The source code of QuickhullDisk is freely available from Mendeley Data and a GUI-version from Voronoi Diagram Research Center, Hanyang University (http://voronoi.hanyang.ac.kr/).

الهيكل المحدب هو واحد من أهم البنى الأساسية في الهندسة وقد تمت دراسة بنائه على نطاق واسع. هناك العديد من الأعمال السابقة على بدن النقاط المحدبة. ومع ذلك، لم يتم تناول نظيرتها للنقاط المرجحة بشكل كافٍ على الرغم من التطبيقات المهمة. نقدم هنا خوارزمية بسيطة وسريعة، QuickhullDisk، للبدن المحدب لمجموعة من الأقراص في R2 من خلال تعميم خوارزمية Quickhull للنقاط. تستغرق QuickhullDisk وقت O(nlog n) في المتوسط ووقت O(mn) في أسوأ الحالات حيث يمثل m عدد الأقراص القصوى التي تساهم في حدود الهيكل المحدب للأقراص n. تتطابق هذه التعقيدات الزمنية مع تلك الخاصة بخوارزمية الهيكل السريع للنقاط في R2. تُظهر النتيجة التجريبية أن خوارزمية QuickhullDisk المقترحة تعمل بشكل أسرع بكثير من الخوارزمية الإضافية للوقت O(nlog n)، التي اقترحها Devillers و Golin في عام 1995، خاصة بالنسبة للبيانات الضخمة. QuickhullDisk أسرع بحوالي 2.6 مرة من الخوارزمية الإضافية للأقراص العشوائية وأسرع 1.2 مرة حتى بالنسبة لمجموعات الأقراص حيث تكون جميع الأقراص متطرفة. يرجع هذا التسريع إلى أن العملية الهندسية الأساسية لخوارزمية QuickhullDisk هي مسند لموقع نقطة w.r.t خط وأسرع بكثير من الخوارزمية الإضافية. يتوفر الكود المصدري لـ QuickhullDisk مجانًا من بيانات مندلي ونسخة واجهة المستخدم الرسومية من مركز أبحاث مخطط فورونوي، جامعة هانيانغ (http://voronoi.hanyang.ac.kr/).