Witness (Delaunay) graphs

Agarwal, 2006, Efficient algorithms for bichromatic separability, ACM Transactions on Algorithms, 2, 209, 10.1145/1150334.1150338 Agarwal, 2002, Motion planning for a convex polygon in a polygonal environment, Discrete and Computational Geometry, 22, 201, 10.1007/PL00009455 Ahn, 2004, Competitive facility location: the Voronoi game, Theoretical Computer Science, 310, 457, 10.1016/j.tcs.2003.09.004 O. Aichholzer, R. Fabila-Monroy, T. Hackl, M. van Kreveld, A. Pilz, P. Ramos, B. Vogtenhuber, Blocking Delaunay triangulations, in: Proc. 22nd Annual Canadian Conference on Computational Geometry CCCG 2010, Winnipeg, Manitoba, Canada, 2010, pp. 21–24. B. Aronov, M. Dulieu, F. Hurtado, Witness rectangle graphs, manuscript, 2010; abstract, in: Proc. 20th Annual Fall Workshop on Computational Geometry, Oct. 29–30, Stony Brook, USA, 2010. B. Aronov, M. Dulieu, F. Hurtado, Witness Gabriel graphs, Computational Geometry: Theory and Applications, in press. A preliminary version is available at arXiv:1008.1051v1. Aurenhammer, 2000, Voronoi diagrams, 201 Di Battista, 1994, Proximity drawability: A survey, vol. 894, 328 Di Battista, 2006, The strength of weak proximity, Journal of Discrete Algorithms, 4, 384, 10.1016/j.jda.2005.12.004 de Berg, 1992, A general approach to dominance in the plane, Journal of Algorithms, 13, 274, 10.1016/0196-6774(92)90019-9 de Berg, 2008 Bose, 1993, Characterizing proximity trees, 9 Bose, 1995, Proximity constraints and representable trees, vol. 894, 340 Brandstädt, 1999, Graph classes: A survey, vol. 3 Chartrand, 2004 J. Czyzowicz, E. Kranakis, J. Urrutia, Dissections, cuts, and triangulations, in: Proc. of the 11th Canadian Conference on Computational Geometry, 1999, pp. 154–157. Dehne, 2005, Maximizing a Voronoi region: The convex case, International Journal on Computational Geometry and Applications, 15, 463, 10.1142/S0218195905001786 Dillencourt, 1990, Toughness and Delaunay triangulations, Discrete and Computational Geometry, 5, 575, 10.1007/BF02187810 Dillencourt, 1990, Realizability of Delaunay triangulations, Information Processing Letters, 33, 283, 10.1016/0020-0190(90)90210-O Dillencourt, 1996, Graph-theoretical conditions for inscribability and Delaunay realizability, Discrete Mathematics, 161, 63, 10.1016/0012-365X(95)00276-3 Dobkin, 1983, Fast detection of polyhedral intersections, Theoretical Computer Science, 27, 241, 10.1016/0304-3975(82)90120-7 Dobkin, 1985, A linear algorithm for determining the separations of convex polyhedra, J. Algorithms, 6, 381, 10.1016/0196-6774(85)90007-0 Dobkin, 1990, Determining the separation of preprocessed polyhedra—a unified approach, vol. 443, 400 Dobkin, 1993, Computing the intersection depth of polyhedra, Algorithmica, 9, 518, 10.1007/BF01190153 M. Dulieu, Ph.D. thesis, in preparation. Polytechnic Institute of NYU, Department of Computer Science and Engineering. Dushnik, 1941, Partially ordered sets, American Journal of Mathematics, 63, 600, 10.2307/2371374 Edelsbrunner, 1986, Voronoi diagrams and arrangements, Discrete Comput. Geom., 1, 25, 10.1007/BF02187681 Edelsbrunner, 1986, Constructing arrangements of lines and hyperplanes with applications, SIAM J. Comput., 15, 341, 10.1137/0215024 Fisk, 1978, A short proof of Chvátalʼs watchman theorem, J. Combinatorial Theory Series B, 24, 374, 10.1016/0095-8956(78)90059-X Fortune, 1992, Voronoi diagrams and Delaunay triangulations, 193 Ichino, 1985, The relative neighborhood graph for mixed feature variables, Pattern Recognition, 18, 161, 10.1016/0031-3203(85)90040-8 Jacobson, 1995, Trees that are sphere of influence graphs, Appl. Math. Letters, 8, 89, 10.1016/0893-9659(95)00091-4 Jaromczyk, 1992, Relative neighborhood graphs and their relatives, Proc. IEEE, 80, 1502, 10.1109/5.163414 Katchalski, 1988, On empty triangles determined by points in the plane, Acta Math. Hungar., 51, 23, 10.1007/BF01903339 D. Kratsch, R.M. McConnell, K. Mehlhorn, J.P. Spinrad, Certifying algorithms for recognizing interval graphs and permutations graphs, in: Proceedings of the Fourteenth Annual ACM–SIAM Symposium on Discrete Algorithms, 2003, pp. 158–167. Lambert, 1997, An optimal algorithm for realizing a Delaunay triangulation, Information Processing Letters, 51, 245, 10.1016/S0020-0190(97)00071-9 G. Liotta, Proximity drawings, in: R. Tamassia (Ed.), Handbook of Graph Drawing and Visualization, Chapman & Hall/CRC Press, Chapter 4, in press. Liotta, 2003, Voronoi drawings of trees, Computational Geometry Theory and Applications, 24, 147, 10.1016/S0925-7721(02)00137-2 Liotta, 1998, The rectangle of influence drawability problem, Computational Geometry Theory and Applications, 10, 1, 10.1016/S0925-7721(97)00018-7 McConnell, 1999, Modular decomposition and transitive orientation, Discrete Math., 201, 189, 10.1016/S0012-365X(98)00319-7 McMorris, 2000, Sphere-of-attraction graphs, Congressus Numerantium, 142, 149 Mehlhorn, 1984, Multi-dimensional Searching and Computational Geometry Monma, 1992, Transitions in geometric minimum spanning trees, Discrete Comput. Geom., 8, 265, 10.1007/BF02293049 Sakai, 2007, Covering the convex quadrilaterals of point sets, Graphs and Combinatorics, 23, 343, 10.1007/s00373-007-0717-0 Sugihara, 1994, Simpler proof of a realizability theorem on Delaunay triangulations, Information Processing Letters, 50, 173, 10.1016/0020-0190(94)00027-1 Toussaint, 2003, Open problems in geometric methods for instance-based learning, vol. 2866, 273 Yao, 1991, Lower bounds for algebraic computation trees with integer inputs, SIAM Journal on Computing, 20, 655, 10.1137/0220041