
4.6. BEYOND THIS CHAPTER 145
Dulieu, and Hurtado [ADH] show an O(n
2
log m)-time algorithm that receives as
input a str aight-line dr awing Γ with n vertices and m edges and checks whether
Γ is a negative witness Gabriel drawing for some set of witness points. If the
answer is affirmative, the algorithm also r etu r n s th e witness points.
Acknowledgments
This chapter extends and updates an early survey on proximity drawings co-authored by
Giuseppe Di Battista, William Lenhart, and me [DLL95]. I t hank Boris Aronov, Ferran
Hurtado, and Sue H. Whitesides for their insights and constructive comments on earlier
versions of this chapter. Work supported in