Aarhus University Seal / Aarhus Universitets segl

Bryan T. Wilkinson

Revisiting visibility in the plane

Research output: Contribution to conferencePaperResearchpeer-review

Abstract We consider two closely related problems: computing the region visible from a point
amid simple polygonal obstacles and computing the lower envelope of a set of disjoint
segments. Visibility problems such as these were proposed and promptly solved in the
late'80s and early'90s before the widespread popularity of the word RAM model. All
previously published algorithms thus run in Ω (n log n) time, although they can be sped up in
the word RAM model to some extent by substituting appropriate word RAM data structures
Original languageEnglish
Publication year2015
Number of pages15
Publication statusPublished - 2015
EventInternational Symposium on Computational Geometry - Eindhoven, Netherlands
Duration: 22 Jun 201525 Jun 2015
Conference number: 31


ConferenceInternational Symposium on Computational Geometry

See relations at Aarhus University Citationformats

ID: 84354731