{"entities":{"Q4023786":{"pageid":6053550,"ns":120,"title":"Item:Q4023786","lastrevid":108220841,"modified":"2026-11-05T11:41:33Z","type":"item","id":"Q4023786","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 108318"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4023786$5A0562A8-358A-4CE5-B064-924EBBB07043","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a640c7771d3f08cec184a87f33982dae45fa411c","datavalue":{"value":"0780.68112","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4023786$1EDA1E8D-B6AD-4310-987A-5E4D20B1FE70","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1332fbdecf1548aae794777b69e753d9df2ed51","datavalue":{"value":{"entity-type":"item","numeric-id":1336743,"id":"Q1336743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4023786$CF642E09-0273-4D75-9F7A-16E11CD5C022","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4f64992dbeef321276c91b04bb85fa175c4114d8","datavalue":{"value":{"time":"+1993-01-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4023786$DB7F48B6-3F35-4FB4-A382-30DEE3F40261","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4023786$1C846726-A98E-4245-8A60-D3F44E3662C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4023786$AFDF2C14-A959-44B1-AFA4-EC2A643EE152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"24aafcf24a21bd70cd3b62d3f5f72a6d0d82d816","datavalue":{"value":"68-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4023786$96DDA8FB-07D6-4D70-9179-83A8E9B2B083","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"77dc13769f8b03f97ff7e87d8cf6b41c06daab0c","datavalue":{"value":"108318","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4023786$77956D76-AF6E-4516-B6AE-2D4B2BA6CC70","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2a942004e7c3ebf174ed889f18fd8e1f8b9b24b","datavalue":{"value":"Voronoi diagrams","type":"string"},"datatype":"string"},"type":"statement","id":"Q4023786$44E7FA12-6680-4483-A569-4FFABB17E830","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4023786$9AEF2AE4-15C5-45A7-AF5B-CA87AAC5733E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db4c4ec4fac679a180bd4783304a028ce64fbcd8","datavalue":{"value":{"entity-type":"item","numeric-id":4694724,"id":"Q4694724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fbb75f116e574e6dc52d4bf8dd7df54c5c78e0f","datavalue":{"value":{"amount":"+0.8866593837738037","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4023786$7E2D2A72-EA6A-4243-B263-7573A8D7BAEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ecb0b9bd12dc5d48068c4720e4f22fd3cf8779c","datavalue":{"value":{"entity-type":"item","numeric-id":2367408,"id":"Q2367408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bfb97aa49d62b1b1d4a15dca3131ca3507db4b6","datavalue":{"value":{"amount":"+0.8792954683303833","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4023786$33DFC0FF-334B-4FA2-B32E-D7414AA55E04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"886e6e4437d155cd26a4c35d7a6133f737f3a9ce","datavalue":{"value":{"entity-type":"item","numeric-id":5056158,"id":"Q5056158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64ba7bd7ae71f978ee929fc002f5edf069238cb9","datavalue":{"value":{"amount":"+0.8789983987808228","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4023786$5F80E4BB-D74E-4FE9-B6DC-D01D58FB1A70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcec1f8c3efcdb6d5763d4a96a8ca090da852bbb","datavalue":{"value":{"entity-type":"item","numeric-id":3212328,"id":"Q3212328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10abe896a4edbe028b6cb08241bad7de78af88f8","datavalue":{"value":{"amount":"+0.8762051463127136","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4023786$43D8ACB6-4C25-4045-AB84-B88D5B05BF48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3398b0bd700a1520490b9eb542553ebc4560b087","datavalue":{"value":{"entity-type":"item","numeric-id":4513216,"id":"Q4513216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a112e94ddec1aad5048ce67f23d35fc10673460","datavalue":{"value":{"amount":"+0.8760724067687988","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4023786$0E32A86B-C257-4F81-B371-69D3D850B091","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d98543399f3a59e2198d7b809d34380890b8bdd8","datavalue":{"value":"Das Voronoi-Diagramm von \\(n\\) Objekten \\(p_ 1,...,p_ n\\) ist eine Partition der euklidischen Ebene in Regionen, je eine zu jedem \\(p_ i\\), so da\u00df die Region von \\(p_ i\\) alle Punkte der Ebene enth\u00e4lt, die n\u00e4her bei \\(p_ i\\) liegen als bei jedem anderen \\(p_ j\\). Voronoi-Diagramme wurden zuerst f\u00fcr Gitterpunkte in der Zahlentheorie betrachtet; wegen ihrer zahlreichen Anwendungen spielen sie heute eine herausragende Rolle in der Informatik, besonders in der Algorithmischen Geometrie und der Bewegungsplanung, aber auch in anderen Wissenschaften. Das Problem besteht darin, das Voronoi-Diagramm m\u00f6glichst schnell und mit m\u00f6glichst wenig Speicherplatz zu berechnen. Hierzu ist die Kenntnis seiner strukturellen Eigenschaften erforderlich. In den letzten 15 Jahren wurden in der Literatur zahlreiche Varianten des Voronoi-Diagramms studiert, die sich durch Wahl von Objekten \\(p_ i\\) verschiedenen Typs, durch Zugrundelegen eines nicht-euklidischen Abstandsbegriffs oder in h\u00f6herdimensionalen R\u00e4umen ergeben. Eine weitere wichtige Verallgemeinerung besteht in den Voronoi-Diagrammen \\(k\\)- ter Ordnung, bei denen jeder Teilmenge von \\(k\\) Objekten die Region derjenigen Punkte zugeordnet wird, die n\u00e4her an jedem dieser \\(k\\) Objekte liegen als an jedem der \u00fcbrigen \\(n-k\\). Nachdem zun\u00e4chst nur die Verh\u00e4ltnisse im statischen Fall, wo alle \\(n\\) Objekte von vornherein bekannt sind, untersucht worden waren, hat man sich in den letzten 4 Jahren mit der dynamischen Situation besch\u00e4ftigt, bei der Objekte sukzessive eingef\u00fcgt und entfernt werden k\u00f6nnen; die jeweils erforderlichen \u00c4nderungen des Diagramms sollen m\u00f6glichst schnell ausgef\u00fchrt werden. In der vorliegenden Dissertation wird eine andere, ebensowichtige Art der Dynamisierung untersucht: die Objektmenge ist fest, aber die Objekte bewegen sich auf stetigen Bahnen in der Ebene. Es soll das jeweils aktuelle Voronoi-Diagramm aufrechterhalten werden. Im ersten Kapitel seiner Arbeit gibt der Verf. zun\u00e4chst eine sehr ausf\u00fchrliche \u00dcbersicht \u00fcber das statische Voronoi-Diagramm, seine geometrischen Anwendungen, \u00fcber die bekannten effizienten Algorithmen zu seiner Konstruktion und die bisher untersuchten Varianten im statischen Fall. Im zweiten Kapitel wird das ``dynamische'' Voronoi-Diagramm von \\(n\\) Punkten untersucht, die sich auf stetigen Bahnen kollisionsfrei in der Ebene bewegen. Der Autor zeigt, da\u00df eine solche Bewegung lokal fast \u00fcberall nur eine Deformation des aktuellen Voronoi-Diagramms bewirkt. Zu \u00c4nderungen seiner kombinatorischen Struktur (und nur auf diese kommt es an) kommst es nur dann, wenn 4 Punkte konzentrisch oder 3 Punkte kollinear sind. F\u00fcr die weitere Untersuchung nimmt der Autor an, da\u00df solche Ereignisse f\u00fcr jedes Quadrupel bzw. Tripel von Punkten h\u00f6chstens \\(s\\) mal vorkommen, wobei \\(s\\) eine Konstante ist. Die Voraussetzung ist deutlich sch\u00e4cher als die bisher in der - sp\u00e4rlichen - Literatur zu diesem Thema verfolgten Ans\u00e4tze. Sie ist insbesondere erf\u00fcllt f\u00fcr polynomiale Bahnen mit beschr\u00e4nktem Grad. Mit diesen Annahmen kann der Autor jedes mit Struktur\u00e4nderung verbundene Ereignis in worst-case Zeit \\(O(\\log n)\\) bearbeiten. Es wird gezeigt, da\u00df diese Schranke erreicht werden kann, selbst wenn sich nur ein Punkt geradlinig bewegt und die \u00fcbrigen fest bleiben. Zusammen mit der Berechnung des Voronoi-Diagramms der Anfangskonfiguration in Zeit \\(O(n\\log n)\\) und dem linearen Speicherplatzbedarf ist dies der erste bekannte optimale Algorithmus zur L\u00f6sung des gestellten Problems. Es stellt sich die Frage, wieviele topologische Ereignisse auftreten k\u00f6nnen. Eine naive Absch\u00e4tzung ergibt \\(O(n^ 4)\\). Mit Hilfe eines eleganten Abz\u00e4hlarguments gelingt es, \\(O(n^ 2\\lambda_ s(n))\\) als nichttriviale obere Schranke nachzuweisen; hierbei bedeutet \\(\\lambda_ s(n)\\) die maximale L\u00e4nge einer Davenport-Schinzel-Sequenz der Ordnung \\(s\\) aus \\(n\\) Symbolen. Auch dieses Ergebnis, das vom Autor in Zusammenarbeit mit \\textit{J. S. B. Mitchell} und \\textit{L. Guibas} erzielt wurde, verbessert die bisher bekannten Resultate. Ob die neue Schranke dicht ist, stellt ein reizvolles Problem f\u00fcr die weitere Forschung dar. Im dritten Kapitel wird der vorgestellte Ansatz auf zwei Arten verallgemeinert: Anstelle von Punkten werden \\(n\\) konvexe Polygone betrachtet, die kollisionsfrei l\u00e4ngs stetiger Bahnen verschoben werden d\u00fcrfen, und f\u00fcr diese werden die Voronoi-Diagramme aller Ordnungen \\(k,1\\leq k\\leq n-1\\), gleichzeitig aufrechterhalten. Die Eigenschaften statischer Voronoi-Diagramme konvexer Polygone waren vom Autor bereits in seiner Diplomarbeit untersucht worden. Im Gegensatz zum Fall punktf\u00f6rmiger Objekte k\u00f6nnen sich hier die Bisektoren von drei Polygonen in zwei Punkten (statt in einem) schneiden. F\u00fcr \\(n\\) bewegte konvexe Polygone lassen sich alle Diagramme \\(k\\)-ter Ordnung, \\(1\\leq k\\leq n-1\\), in optimaler Zeit \\(O(\\log n)\\) pro Ereignis unterhalten. Hierzu wird \\(O(n^ 3)\\) Speicherplatz ben\u00f6tigt und \\(O(n^ 4)\\) Vorbereitungszeit f\u00fcr die Berechnung der Anfangsdiagramme. Nur von der letzten Schranke ist nicht bekannt, ob sie dicht ist. Da\u00df f\u00fcr die Struktur\u00e4nderungen nur logarithmische Zeit ben\u00f6tigt wird, liegt daran, da\u00df jede \u00c4nderung h\u00f6chstens 3 konsekutive Ordnungen involviert. Die maximale Anzahl von Ereignissen bei gleichzeitiger Verwaltung aller \\(k\\)-Voronoi-Diagramme ist durch \\(O(n^ 4)\\) beschr\u00e4nkt; diese Schranke wird bereits f\u00fcr Punkte angenommen. Im vierten Kapitel werden schlie\u00dflich einige klassische geometrische Probleme (wie etwa die Konstruktion der konvexen H\u00fclle oder eines minimalen spannenden Baumes) unter dynamischen Gesichtspunkten betrachtet, deren L\u00f6sungen im statischen Fall in linearer Zeit aus dem Voronoi-Diagramm abgeleitet werden k\u00f6nnen. Hierbei tritt folgendes Problem auf: Nicht jedes f\u00fcr das Voronoi-Diagramm wichtige Ereignis ist auch f\u00fcr das abgeleitete Problem relevant; hier gibt der Autor zum Teil echt kleinere Schranken an und schl\u00e4gt vor, nur die relevanten Ereignisse zu bearbeiten.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4023786$2C7A200B-D608-4E12-B605-D86141912AD6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4023786","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4023786"}}}}}