3 Search Results for "Cook, Atlas F."


Document
The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation

Authors: Wouter van Toll, Atlas F. Cook IV, Marc van Kreveld, and Roland Geraerts

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)


Abstract
We describe and demonstrate the Explicit Corridor Map (ECM), a navigation mesh for path planning and crowd simulation in virtual environments. For a bounded 2D environment with polygonal obstacles, the ECM is the medial axis of the free space annotated with nearest-obstacle information. It can be used to compute short and smooth paths for disk-shaped characters of any radius. It is also well-defined for multi-layered 3D environments that consist of connected planar layers. We highlight various operations on the ECM, such as dynamic updates, visibility queries, and the computation of paths (indicative routes). We have implemented the ECM as the basis of a real-time crowd simulation framework with path following and collision avoidance. Our implementation has been successfully used to simulate real-life events involving large crowds of heterogeneous characters. The enclosed demo application displays various features of our software.

Cite as

Wouter van Toll, Atlas F. Cook IV, Marc van Kreveld, and Roland Geraerts. The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 70:1-70:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{vantoll_et_al:LIPIcs.SoCG.2016.70,
  author =	{van Toll, Wouter and Cook IV, Atlas F. and van Kreveld, Marc and Geraerts, Roland},
  title =	{{The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{70:1--70:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.70},
  URN =		{urn:nbn:de:0030-drops-59622},
  doi =		{10.4230/LIPIcs.SoCG.2016.70},
  annote =	{Keywords: Medial axis, Navigation mesh, Path planning, Crowd simulation}
}
Document
Shortest Path Problems on a Polyhedral Surface

Authors: Carola Wenk and Atlas F. Cook

Published in: Dagstuhl Seminar Proceedings, Volume 9111, Computational Geometry (2009)


Abstract
We develop algorithms to compute edge sequences, Voronoi diagrams, shortest path maps, the Fréchet distance, and the diameter for a polyhedral surface. Distances on the surface are measured either by the length of a Euclidean shortest path or by link distance. Our main result is a linear-factor speedup for computing all shortest path edge sequences on a convex polyhedral surface.

Cite as

Carola Wenk and Atlas F. Cook. Shortest Path Problems on a Polyhedral Surface. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{wenk_et_al:DagSemProc.09111.5,
  author =	{Wenk, Carola and Cook, Atlas F.},
  title =	{{Shortest Path Problems on a Polyhedral Surface}},
  booktitle =	{Computational Geometry},
  pages =	{1--30},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9111},
  editor =	{Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09111.5},
  URN =		{urn:nbn:de:0030-drops-20332},
  doi =		{10.4230/DagSemProc.09111.5},
  annote =	{Keywords: Shortest paths, edge sequences}
}
Document
Geodesic Fréchet Distance Inside a Simple Polygon

Authors: Carola Wenk and Atlas F. Cook

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)


Abstract
We unveil an alluring alternative to parametric search that applies to both the non-geodesic and geodesic Fr{'\e}chet optimization problems. This randomized approach is based on a variant of red-blue intersections and is appealing due to its elegance and practical efficiency when compared to parametric search. We present the first algorithm for the geodesic Fr{'\e}chet distance between two polygonal curves $A$ and $B$ inside a simple bounding polygon $P$. The geodesic Fr{'\e}chet decision problem is solved almost as fast as its non-geodesic sibling and requires $O(N^{2log k)$ time and $O(k+N)$ space after $O(k)$ preprocessing, where $N$ is the larger of the complexities of $A$ and $B$ and $k$ is the complexity of $P$. The geodesic Fr{'\e}chet optimization problem is solved by a randomized approach in $O(k+N^{2log kNlog N)$ expected time and $O(k+N^{2)$ space. This runtime is only a logarithmic factor larger than the standard non-geodesic Fr{'\e}chet algorithm (Alt and Godau 1995). Results are also presented for the geodesic Fr{'\e}chet distance in a polygonal domain with obstacles and the geodesic Hausdorff distance for sets of points or sets of line segments inside a simple polygon $P$.

Cite as

Carola Wenk and Atlas F. Cook. Geodesic Fréchet Distance Inside a Simple Polygon. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 193-204, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{wenk_et_al:LIPIcs.STACS.2008.1330,
  author =	{Wenk, Carola and Cook, Atlas F.},
  title =	{{Geodesic Fr\'{e}chet Distance Inside a Simple Polygon}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{193--204},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1330},
  URN =		{urn:nbn:de:0030-drops-13303},
  doi =		{10.4230/LIPIcs.STACS.2008.1330},
  annote =	{Keywords: Fr\'{e}chet Distance, Geodesic, Parametric Search, Simple Polygon}
}
  • Refine by Author
  • 2 Cook, Atlas F.
  • 2 Wenk, Carola
  • 1 Cook IV, Atlas F.
  • 1 Geraerts, Roland
  • 1 van Kreveld, Marc
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Crowd simulation
  • 1 Fréchet Distance
  • 1 Geodesic
  • 1 Medial axis
  • 1 Navigation mesh
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2008
  • 1 2009
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail