Zusammenfassung
In diesem Beitrag geht es uns darum, an einigen wenigen Beispielen aus der räumlichen Analyse grundlegende Entwurfstechniken für Algorithmen und Werkzeuge der kombinatorischen Optimierung zu illustrieren. Außerdem wollen wir ein Minimum an theoretischem Unterbau vermitteln. Damit hoffen wir, dass es dem Leser, der Leserin gelingt, räumliche Probleme mit Methoden der Informatik bewusst und damit erfolgreich zu lösen. Wir halten es für besonders wichtig, dass man neue Probleme sorgfältig mathematisch modelliert und mittels exakter Algorithmen das eigene Modell wenigstens auf kleinen Instanzen überprüft, bevor man sich schnellen Heuristiken zuwendet, um große Instanzen zu lösen.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Literatur
Alt, H., Efrat, A., Rote, G., Wenk, C.: Matching planar maps. J. Algorithms 49(2), 262–283 (2003). https://doi.org/10.1016/S0196-6774(03)00085-3
Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Comput. Geom. Theory Appl. 9(1–2), 3–24 (1998). https://doi.org/10.1016/S0925-7721(97)00014-X
Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Techn. Ber. 388, Graduate School of Industrial Administration, Carnegie Mellon University (1976)
Clark, B.N., Colbourn C.J., Johnson D.S.: Unit disk graphs. Discret. Math. 86(1–3), 165–177 (1990). https://doi.org/10.1016/0012-365X(90)90358-O
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Algorithmen – Eine Einführung, 4. Aufl. Oldenbourg, München (2013)
Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)
Das, G.K., De, M., Kolay, S., Nandy, S.C., Sur-Kolay, S.: Approximation algorithms for maximum independent set of a unit disk graph. Inform. Process. Lett. 115(3), 439–446 (2015). https://doi.org/10.1016/j.ipl.2014.11.002
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3. Aufl. Springer, Berlin (2008). https://doi.org/10.1007/978-3-540-77974-2
Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inform. Process. Lett. 12(3), 133–137 (1981). https://doi.org/10.1016/0020-0190(81)90111-3
Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., San Francisco (1990)
Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Am. Math. Soc. 64, 275–278 (1958). https://doi.org/10.1007/978-3-540-68279-0_4
Haunert, J.H., Wolff, A.: Optimal simplification of building ground plans. In: Proceedings of 21st Congress International Society Photogrammetry Remote Sensing (ISPRS’08), Technical Commision II/3. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, Bd. XXXVII, Part B2, S. 373–378, Beijing (2008). http://www.isprs.org/proceedings/XXXVII/congress/2_pdf/3_WG-II-3/01.pdf
Haunert, J.H., Wolff, A.: Area aggregation in map generalisation by mixed-integer programming. Int. J. Geogr. Inform. Sci. 24(12), 1871–1897 (2010). https://doi.org/10.1080/13658810903401008
Hsiao, J.Y., Tang, C.Y., Chang, R.S.: An efficient algorithm for finding a maximum weight 2-independent set on interval graphs. Inform. Process. Lett. 43(5), 229–235 (1992). https://doi.org/10.1016/0020-0190(92)90216-I
Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373–395 (1984). https://doi.org/10.1007/BF02579150
Kirkpatrick, S., Gelatt Jr., C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983). https://doi.org/10.2307/1690046
Krumke, S.O., Noltemeier, H.: Graphentheoretische Konzepte und Algorithmen, 3. Aufl. Vieweg+Teubner (2012). https://doi.org/10.1007/978-3-8348-2264-2
Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982). https://doi.org/10.1137/0211025
Michiels, W., Aarts, E., Korst, J.: Theoretical Aspects of Local Search. Springer, Berlin/New York (2007). https://doi.org/10.1007/978-3-540-35854-1
Niemeier, W.: Ausgleichungsrechnung, 2. Aufl. De Gruyter, Berlin (2008)
Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover, Mineola (1998)
Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001). https://doi.org/10.1007/978-3-662-04565-7
Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge/New York (2011)
Wolff, A.: Graph drawing and cartography. In: Tamassia, R. (Hrsg.) Handbook of Graph Drawing and Visualization, Kap. 23, S. 697–736. CRC Press, Boca Raton (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature
About this chapter
Cite this chapter
Haunert, JH., Wolff, A. (2019). Räumliche Analyse durch kombinatorische Optimierung. In: Sester, M. (eds) Geoinformatik. Springer Reference Naturwissenschaften . Springer Spektrum, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47096-1_69
Download citation
DOI: https://doi.org/10.1007/978-3-662-47096-1_69
Published:
Publisher Name: Springer Spektrum, Berlin, Heidelberg
Print ISBN: 978-3-662-47095-4
Online ISBN: 978-3-662-47096-1
eBook Packages: Life Science and Basic Disciplines (German Language)