HAL - INRIA :: [inria-00192927, version 1] Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint

inria-00192927, version 1

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint

Olivier Devillers () ¹, Vida Dujmovic ², Hazel Everett () ³, Samuel Hornus ⁴, Sue Whitesides ⁵, Steve Wismath ⁶

International Journal of Computational Geometry & Applications 17, 4 (2007) 297-304

Abstract: Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves. In linear space, and after O(n log n) preprocessing time, our solution maintains the view at a cost of O(log n) amortized time (resp. O(log^2 n) worst case time) for each change. Our algorithm can also be used to maintain the set of points sorted according to their distance to q.

1: GEOMETRICA (INRIA Sophia Antipolis)
INRIA
2: Department of Mathematics and Statistics [Mac Gill]
Mac Gill University
3: VEGAS (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
4: ARTIS (INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann)
CNRS : FR71 – INRIA – Laboratoire Jean Kuntzmann – CNRS : UMR5224 – Université Joseph Fourier - Grenoble I – Institut National Polytechnique de Grenoble (INPG)
5: School of Computer Science [Quebec] (SOCS)
McGill University
6: Department of Mathematics and Computer Science
University of Lethbridge

inria-00192927, version 1
http://hal.inria.fr/inria-00192927
oai:hal.inria.fr:inria-00192927
From: Olivier Devillers <>
Submitted on: Thursday, 29 November 2007 17:20:27
Updated on: Tuesday, 4 December 2007 20:32:38

See detailed view

Associated documents

PDF :

DOI: 10.1142/S0218195907002343

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles in peer-reviewed journal</head>
<biblStruct type="article" xml:id="inria-00192927"><analytic>
<author><persName><forename>Olivier</forename><surname>Devillers</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">GEOMETRICA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Vida</forename><surname>Dujmovic</surname></persName>
<affiliation>
<orgName type="team">Department of Mathematics and Statistics [Mac Gill]</orgName>
<country>CA</country>
<orgName type="institution">Mac Gill University</orgName>
</affiliation>
</author>
<author><persName><forename>Hazel</forename><surname>Everett</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">VEGAS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Samuel</forename><surname>Hornus</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann</orgName>
<orgName type="team">ARTIS</orgName>
<country>FR</country>
<orgName type="institution">CNRS : FR71</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Laboratoire Jean Kuntzmann</orgName>
<orgName type="institution">CNRS : UMR5224</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Institut National Polytechnique de Grenoble (INPG)</orgName>
</affiliation>
</author>
<author><persName><forename>Sue</forename><surname>Whitesides</surname></persName>
<affiliation>
<orgName type="laboratory">SOCS</orgName>
<orgName type="team">School of Computer Science [Quebec]</orgName>
<country>CA</country>
<orgName type="institution">McGill University</orgName>
</affiliation>
</author>
<author><persName><forename>Steve</forename><surname>Wismath</surname></persName>
<affiliation>
<orgName type="team">Department of Mathematics and Computer Science</orgName>
<country>CA</country>
<orgName type="institution">University of Lethbridge</orgName>
</affiliation>
</author>
<title type="main" level="a">Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint</title></analytic><monogr><title level="j" type="main">International Journal of Computational Geometry and Applications</title><imprint><publisher>World Scientific</publisher><biblScope type="publicationDate">2007-00-00</biblScope><biblScope type="vol">17</biblScope><biblScope type="issue">4</biblScope><biblScope type="pp">297-304</biblScope></imprint></monogr><idno type="doi">10.1142/S0218195907002343</idno><idno type="HALid">http://hal.inria.fr/inria-00192927</idno><idno type="HALFile">http://hal.inria.fr/inria-00192927/PDF/hal.pdf</idno></biblStruct>
</listBibl>
</listBibl>